Understanding Time Complexity

Understanding Time Complexity

You can read a growth curve, you know the formal definition, and you know which bound drives which design. This page closes the loop with the skill all of that depends on: given a piece of code, how do you actually derive its time complexity? Not recognize it — derive it, from loop structure, on examples where the answer is not obvious at a glance. This is the counting method, and getting it wrong by a whole class is the most common analysis mistake in real reviews.

The method, in four steps

1. Name the input size. Usually n = array length or node count. If two independent inputs drive the cost, name both — a graph is O(V + E), never a single collapsed n.
2. Find the basic operation that runs most often (a comparison, an array access) and count it.
3. Count the repetitions as a function of n, respecting structure: sequential blocks add; nested blocks multiply — except when an inner bound depends on the outer index (then you need a summation) or when a loop index is multiplied/divided (then it is logarithmic).
4. Drop constants and low-order terms to name the class. (The formal justification for that last step is on Big-O Notation.)

Steps 1–2 are bookkeeping; step 3 is where the judgment lives. The next three examples are exactly the cases where "just multiply the loops" gives the wrong answer.

Worked example 1 — a dependent inner bound needs a sum, not a product

for i in 1..n:  for j in 1..i:  work()

The inner loop does not run n times; it runs i times, and i climbs from 1 to n. Multiplying "outer n × inner n" overcounts. The honest count is a sum:

∑i=1n i = 1 + 2 + … + n = n(n+1)/2

Concretely: n = 4 → 4·5/2 = 10 inner iterations; n = 8 → 36. Dropping the constant and low-order term, n(n+1)/2 = O(n2). Same class as a full nested loop, but exactly half the work — and recognizing the triangular sum is what lets you count the many algorithms (selection sort, pairwise comparisons over ordered pairs) that have this shape.

Worked example 2 — a multiplied/divided index is logarithmic

while n > 1:  n = n / 2

The counter is not decremented, it is halved. Starting at n, it takes 16 → 8 → 4 → 2 → 1 — ⌊log2n⌋ steps. For n = 16 that is 4 iterations, not 16. Any loop whose index multiplies or divides by a constant factor each step is O(log n), and this is precisely the counting insight behind binary search and balanced-tree height.

Now combine them — the case that trips people up:

for i in 1..n:  j = 1; while j < n: j = j * 2

The outer loop runs n times; the inner (doubling) loop runs ⌈log2n⌉ times each. They nest, so they multiply: n × log2n = O(n log n). At n = 8 that is 8 × 3 = 24; at n = 1024, 1024 × 10 = 10,240. Reading "two loops → O(n2)" here would be wrong by a full class.

The decision the method installs: does this nest actually multiply?

Here is the counting judgment that separates a strong engineer from someone who pattern-matches "nested = O(n2)." Compare two loop nests that look identical:

Genuine O(n2) — inner index resets every outer pass:
for i in 0..n-1:  for j in 0..n-1: work() — the inner loop restarts at 0 for each i, so it truly runs n times × n = n2.

Actually O(n) — inner index never resets (the two-pointer / sliding-window shape):
j = 0; for i in 0..n-1:  while j < n and cond: j++ — j is declared outside and only ever advances. Across all outer iterations combined, the inner loop runs at most n times total, so the whole thing is O(n), not O(n2) — this is amortized counting.

The stakes are not academic. At n = 106, misreading the second nest as O(n2) predicts 1012 operations (~1000 s) when the truth is 106 (~milliseconds) — a million-fold misdiagnosis that would make you reject a correct, fast design as "too slow." The tell is always the same question: does the inner index reset each outer iteration, or does it carry forward? Multiply only when it resets.

Counting across cases, and across recursion

The same method, applied per input scenario, gives best/worst/average. Linear search over n items: best = target first = 1 comparison = Ω(1); worst = target last or absent = n = O(n); average (uniformly random position) = (1+2+…+n)/n = (n+1)/2 = Θ(n). Always state which case.

Recursive code is counted the same way, but the "loop count" becomes a recurrence: mergesort does two half-size recursive calls plus a linear merge, T(n) = 2T(n/2) + O(n). Expanding the recursion tree gives log2n levels each doing O(n) work, so T(n) = O(n log n) — the tree-expansion technique and the Master theorem are the recursion counterpart of these loop-counting rules.

Counting pitfalls

• i *= 2 is log n, not n. Multiplicative index growth is the most-missed logarithm.
• Dependent inner bounds need a summation, not a product — ∑i = n(n+1)/2, not n2 flat.
• Hidden O(n) calls. list.contains(), string concatenation, or array slicing inside a loop each smuggle in an O(n), turning an apparent O(n) loop into O(n2). Count the cost of every call, not just the loops you wrote.
• Non-resetting inner loops are amortized — count total inner iterations across all outer passes, not inner-per-outer times outer.

Key takeaways

• Derive complexity by a fixed method: name n, find the basic op, count with structure (add / multiply / sum / log), then drop constants.
• Structure decides the count: dependent inner bounds are a summation (∑i = n(n+1)/2); a multiplied/divided index is O(log n); combined they give O(n log n).
• The key judgment is amortization: a nested loop is only O(n2) when the inner index resets each pass — a carry-forward inner loop is O(n), a distinction worth a million-fold error at n = 106.
• Apply the method per case for best/worst/average, and per recurrence (T(n) = 2T(n/2)+O(n) = O(n log n)) for recursion; watch for hidden O(n) calls.