Best, average and worst case; analysing loops and recursion

One algorithm, three cases

Linear search looks at items one by one until it finds the target. If the target is the first item, it takes one step: that is the best case, O(1). If the target is last or missing, it checks all n items: the worst case, O(n). On average, for a target that is present at a random position, it checks about n/2 items, which is still O(n).

The worst case is the safe promise: the code will never be slower than this. So when someone says "linear search is O(n)" they mean the worst case. When an interviewer asks for the complexity, give the worst case unless they ask for something else, and mention the average case if it is very different.

Quicksort, which you will meet in Module 6, is the famous example where the cases differ. On average it takes O(n log n). But if the pivot it picks is always the smallest or largest item (for example, always picking the first item of an already sorted list), it degrades to O(n²). Library sorts avoid this problem; Python's sorted() is O(n log n) in the worst case.

Loops that halve or double

A logarithm answers the question "how many times can I halve n before I reach 1?" For n = 8 the answer is 3 (8 → 4 → 2 → 1), so log₂ 8 = 3. Any loop that halves its counter, or doubles it up to n, runs about log₂ n times, so it is O(log n).

def halvings(n):
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps

print(halvings(8), halvings(1000), halvings(10**6))   # Output: 3 9 19

Compare that with i += 2, which only takes n/2 steps: still O(n). Only multiplying or dividing the counter gives a logarithm.

i = 1
count = 0
while i < 1000:
    i *= 2
    count += 1
print(count)   # Output: 10

Recursion trees

A recurrence is an equation that describes the cost of a recursive function in terms of smaller calls. T(n) means "the time for input size n". To solve one, draw a recursion tree: each call is a box, its children are the calls it makes. Add up the work done on each level, then multiply by (or add up over) the number of levels.

• T(n) = T(n/2) + 1, like binary search: one call per level, constant work each, and n halves until 1, so about log₂ n levels. Total O(log n).
• T(n) = 2T(n/2) + n, like merge sort: level 0 has one call doing n work, level 1 has two calls doing n/2 each (n in total), level 2 has four calls doing n/4 each (n again). Every level does n work and there are log₂ n levels, so O(n log n).
• T(n) = 2T(n − 1) + 1, like naive Fibonacci or Tower of Hanoi: the number of calls doubles at every level and there are n levels, so about 2ⁿ calls: O(2ⁿ).

The Master theorem is a shortcut for recurrences of the form T(n) = a·T(n/b) + f(n): a calls, each on 1/b of the input, plus f(n) work to split and combine. Compare f(n) with n^(log_b a). If f(n) is clearly smaller, the answer is n^(log_b a); if they are the same size, multiply by log n; if f(n) is clearly bigger, the answer is f(n). For binary search, a = 1 and b = 2 give n⁰ = 1, the same as f(n) = 1, so O(log n). For merge sort, a = 2 and b = 2 give n¹, the same as f(n) = n, so O(n log n). You rarely need more than this in an interview.

Common mistakes

• Saying "two nested loops, so O(n²)" without checking how far the inner loop runs. Fix: if the inner loop halves or doubles, it is O(n log n); look at the exact bounds.
• Treating i += 2 or i += 100 as logarithmic. Fix: adding a constant is still linear; only multiplying or dividing gives log n.
• Thinking naive recursive Fibonacci is O(n) because n goes down by 1. Fix: each call makes two calls, so the tree doubles at each level: O(2ⁿ).
• Quoting the average case as if it were guaranteed. Fix: say both, for example "O(n log n) on average, O(n²) in the worst case".
• Forgetting work done outside the recursive calls, such as slicing or merging. Fix: that is the f(n) part, and it changes the answer.