Complexity and amortized analysis

Is an O(n) algorithm always faster than an O(n²) one?

No. Big-O describes how the number of steps grows as the input grows, and it drops constant factors on the way. An O(n) routine that does two hundred units of work per element loses to an O(n²) routine that does one unit per pair until n is well past two hundred. What Big-O promises is that a large enough n exists past which the lower order wins, and for interview-sized inputs that n is usually small. Say the order first, then name the constant if it is unusual: heavy per-element work, a big alphabet, a hash that is expensive to compute.

Should I count exact operations, or is the order enough?

The order is the answer; the counting is the argument. An interviewer wants to hear you bound the total work rather than guess: “r moves n times, l only moves forward and never passes r, so that is at most 2n pointer moves”. Then round to O(n). Exact step counts only matter when two candidate solutions share an order and you have to choose between them, or when the constant is the whole difference, such as a scan over 26 letters inside every loop iteration.

What does amortized mean, in one sentence?

It means the expensive steps are rare enough that their cost, spread over all the steps, stays small: an append to a Python list copies the whole block when the block is full, but each doubling buys as many free appends as the items it just copied, so n appends cost O(n) copies in total and O(1) each on average. Amortized is not the same as average-case. Average-case talks about a distribution of inputs, while amortized is a worst-case statement about a whole sequence of operations, with no randomness involved.

Does the recursion stack count toward space complexity?

Yes, and forgetting it is one of the most common ways to get a space answer wrong. Every open call keeps its own frame: parameters, locals, and the place to return to. A recursion over a linked list of n nodes holds n frames at the deepest moment, so it is O(n) space even when it allocates nothing itself. A tree recursion holds one frame per level, so it is O(h) for height h, which is O(log n) for a balanced tree and O(n) for a degenerate one. CPython also caps the depth at around a thousand frames by default, so deep recursion raises RecursionError rather than running slowly.

How do I know which complexity a problem is asking for?

Read the constraint on the input size before you write anything. If n is up to a hundred thousand, a solution that touches every pair does about ten billion units of work and will not pass, so the target is about n or n log n. If n is up to a couple of hundred, an n³ solution is a few million steps and is fine. Saying that out loud at the start (“n is 10⁵, so I need about n log n”) is worth as much as the solution, because it shows you chose the approach rather than recalled it.