Complexity & Big-O

Big-O is just a way of asking 'if the input gets bigger, how much more work do I do?' - not how many seconds it takes on your laptop. Think of cooking for guests: if 1 guest takes 1 step and 10 guests take 10 steps, the work grows in a straight line. But if every guest must shake hands with every other guest, the work grows much faster.

Example: finding a name by flipping a phone book page by page grows with its size - double the pages, double the flips. But opening to the middle and always throwing away half the book finds the name in only a handful of steps. Same goal, wildly different growth - and that difference is exactly what Big-O measures.

Three Greek-letter bounds exist, but interviews almost always mean Big-O describing the worst case.

Two rules collapse messy expressions into a clean class: drop constants (O(2n) → O(n)) and keep only the dominant term (O(n² + n) → O(n²)). Complexity is about the limit as n → ∞, where the biggest term swamps everything else.

Sorted from fastest-growing-slowest to explosive. Memorise this order — it's the y-axis interviewers picture.

The jump from O(n log n) to O(n²) is the line most "can you do better?" questions are about. Anything O(2^n) or worse is only acceptable when n is tiny (n ≤ ~20).

A dynamic array (Java ArrayList, Python list) appends in amortised O(1), even though an occasional append triggers an O(n) resize-and-copy. Why? Because the array doubles its capacity, those expensive resizes happen rarely enough that the average cost per append, spread across n appends, is constant.

Think of it like a phone plan: a few big bills (resizes) averaged over many cheap months (normal appends) gives a low monthly cost. Interviewers love when you say "append is amortised O(1)" rather than incorrectly calling it O(n).

Space complexity counts extra memory your algorithm allocates beyond the input. The output usually doesn't count unless the problem treats it as working memory.

The most-missed source of space is the recursion call stack: each pending recursive call holds a frame. A recursion that goes n deep is O(n) space even if it allocates nothing else. A balanced-tree DFS is O(log n) stack; a skewed tree (or linked-list recursion) is O(n) stack and can overflow.

End every solution with a single, confident sentence in this shape: "This is O(⟨time⟩) time because ⟨dominant work⟩, and O(⟨space⟩) space because ⟨what I allocate⟩."

Examples:

• "O(n) time — one pass over the array — and O(n) space for the hash map."
• "O(n log n) time, dominated by the sort, and O(1) extra space since I sort in place."
• "O(2^n) time because I branch on include/exclude at each element, and O(n) space for the recursion depth."

Always name the dominant term and why it dominates. That 'why' is the signal.