Big-O & Complexity

Growth, not stopwatch

Big-O ignores constants and machine speed and asks: if input doubles, what happens to the work? O(1) unchanged, O(log n) grows by one step, O(n) doubles, O(n log n) slightly more than doubles, O(n^2) quadruples.

Reading complexity from loops

A single pass over n items is O(n). A loop inside a loop over the same data is O(n^2). Halving the range each step is O(log n).

for x in arr:            # O(n)
    print(x)

for i in arr:            # O(n^2)
    for j in arr:
        print(i, j)

lo, hi = 0, len(arr) - 1 # O(log n)
while lo <= hi:
    mid = (lo + hi) // 2
    ...

Time vs space

Space complexity counts extra memory beyond the input — a few variables is O(1), a copy of the array is O(n), a recursion depth of n is O(n) stack space. Interviewers often ask you to trade one for the other.

Quick check: Input goes from 1,000 to 1,000,000. An O(log n) step count roughly...

• Triples
• Grows by ~10 steps
• Grows 1000x