DevPath
Tracks

Big-O and Complexity Analysis

Measure how an algorithm's cost grows with input size, read common complexity classes at a glance, and reason about time, space, and amortized cost.

beginner40 min#big-o#complexity#time#space#amortized

Prerequisites: How to Study Programming

Why it matters

Two programs can both give the right answer, yet one finishes in a blink and the other outlives the universe once the input grows. Big-O gives you a shared vocabulary for that difference. It lets you compare solutions before writing them, spot the bottleneck in a design, and answer the question every interviewer asks: "what is the complexity?"

Intuition

Do not time your program in seconds; seconds depend on the laptop, the language, and the weather. Instead ask: if the input gets ten times bigger, how much more work happens?

  • Finding a name in an unsorted guest list means checking each name: ten times the guests, ten times the work. That is linear.
  • Finding a word in a dictionary by opening to the middle and discarding half each time: a million words need only about 20 steps. Ten times the words add roughly 3 steps. That is logarithmic.
  • Introducing every guest to every other guest: ten times the guests, a hundred times the handshakes. That is quadratic.

Big-O keeps only the shape of that growth and throws away constants and lower-order terms, because for large inputs the shape dominates.

048112input size noperations
O(1)O(log n)O(n)O(n log n)O(n²)O(2ⁿ)
Each curve is the work as n grows. Notice how n² and 2ⁿ shoot up while log n stays almost flat, so the shape, not the constant, decides what is usable.

How it works

Say f(n) is the number of basic steps for an input of size n. We write f(n) = O(g(n)) when, beyond some point, f never grows faster than a constant multiple of g. In practice you apply three rules.

  1. Drop constants: 3n and 100n are both O(n).
  2. Drop lower-order terms: n^2 + 5n + 40 is O(n^2).
  3. Add sequential parts, multiply nested parts: two loops one after the other cost O(n) + O(n) = O(n); a loop inside a loop costs O(n * n).

Common classes, fastest to slowest:

O(1)  <  O(log n)  <  O(n)  <  O(n log n)  <  O(n^2)  <  O(2^n)  <  O(n!)

n = 1,000,000       steps (roughly)
O(log n)            20
O(n)                1,000,000
O(n log n)          20,000,000
O(n^2)              1,000,000,000,000
O(log n)
20 steps
O(n)
1,000,000 steps
O(n log n)
20,000,000 steps
O(n²)
1,000,000,000,000 steps
The same table drawn on a log scale (each gridline is 10 times the last). From log n to n² is a gap of ten orders of magnitude.
OperationTimeNotes
Array index a[i]O(1)Constant, independent of n
Binary search in sorted arrayO(log n)Halve the range each step
Scan a list onceO(n)Touch each item
Efficient sort (merge, heap)O(n log n)Best possible for comparison sorts
Compare every pairO(n^2)Nested loops over the same input
All subsets of n itemsO(2^n)Exponential; only tiny n

Beyond the worst case

  • Best, average, worst: linear search finds its target at once in the best case (O(1)), but we normally quote the worst case (O(n)) because it is a guarantee.
  • Big-Theta and Big-Omega: O is an upper bound, Omega a lower bound, and Theta means both, a tight bound. In casual conversation people say "O(n)" and mean the tight bound.
  • Amortized cost: an operation that is usually cheap but occasionally expensive can still average out. Appending to a doubling dynamic array is O(1) amortized because the rare O(n) resize is paid for by many cheap appends.
  • Space complexity: the same analysis for extra memory. A recursive function that goes n calls deep uses O(n) stack space even if it allocates nothing else.

Reading complexity from code

  • A single loop over n items doing constant work: O(n).
  • A loop where the variable doubles or halves (i *= 2): O(log n).
  • A loop inside a loop, both over n: O(n^2). If the inner loop starts at i + 1, the total is about n^2 / 2, still O(n^2).
  • Two independent inputs, sizes a and b: write O(a + b) or O(a * b), never collapse them into one n.
  • Recursion that splits into two halves and does linear work to combine (merge sort): O(n log n).

Code: counting steps

Rather than trust the rules, count steps. This program counts how many comparisons a linear search and a binary search take to miss a value in a sorted list, and how many pair visits a double loop makes.

def linear_search(a, target):
    steps = 0
    for i, x in enumerate(a):
        steps += 1
        if x == target:
            return i, steps
    return -1, steps
 
def binary_search(a, target):
    lo, hi, steps = 0, len(a) - 1, 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid, steps
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, steps
 
def count_pairs_quadratic(a):
    steps = 0
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            steps += 1
    return steps
 
for n in (1000, 1000000):
    a = list(range(n))
    print(n, "linear", linear_search(a, -1)[1], "binary", binary_search(a, -1)[1])
print("pairs for n=1000:", count_pairs_quadratic(list(range(1000))))

Both versions print:

1000 linear 1000 binary 9
1000000 linear 1000000 binary 19
pairs for n=1000: 499500

A thousand times more data made linear search a thousand times slower but binary search only about two times slower (9 to 19 steps). The pair count, 1000 * 999 / 2, shows the quadratic blow-up.

To feel the difference, here are both searches on the same sorted array of 9 items, looking for 72 (the last one).

2
0
i
5
1
8
2
12
3
16
4
23
5
38
6
56
7
72
8
Linear: check index 0. 2 is not 72. Comparisons so far: 1.
step 1 / 7

Linear search needs 9 comparisons here, binary search only 4. With a million items the gap becomes 1,000,000 versus about 20.

Common pitfalls

  • Hidden costs in built-ins: x in my_list is O(n), string concatenation in a loop can be O(n^2), slicing copies. Know what the library call costs.
  • Confusing average with worst case: a hash table lookup is O(1) on average but O(n) if every key collides. Quicksort is O(n log n) on average and O(n^2) in its worst case.
  • Treating two inputs as one: iterating a grid with r rows and c columns is O(r * c), not O(n^2) unless the grid is square.
  • Forgetting recursion space: the call stack counts. Recursing to depth n is O(n) memory.
  • Counting only loops: sorted(...) inside a loop turns an apparent O(n) into O(n^2 log n).

Practice

Classify these snippets easy

Hint

Count how the loop variable changes and whether loops are nested or sequential.

Show solution

(a) for i in range(n): for j in range(n): work() is O(n^2). (b) i = n; while i > 1: i //= 2 runs about log2(n) times, so O(log n). (c) A loop over n followed by a separate loop over n is O(n + n) = O(n). (d) for i in range(n): for j in range(i): work() does 0 + 1 + ... + (n-1) = n(n-1)/2 steps, O(n^2).

Does the order of ops matter? medium

Hint

Compare sorting then scanning against checking every pair for a duplicate.

Show solution

To find whether a list has duplicates, checking every pair is O(n^2) time and O(1) space. Sorting first costs O(n log n) and then neighbors are compared in O(n), so O(n log n) overall (space depends on the sort). A set gives O(n) time and O(n) space. Each choice trades time for memory; state the trade-off aloud.

Amortized analysis of a counter medium

Hint

How often does bit 0 flip? Bit 1? Bit k?

Show solution

Incrementing a binary counter from 0 to n flips bit k about n / 2^k times. The total flips are n * (1 + 1/2 + 1/4 + ...), below 2n. So the amortized cost per increment is O(1) even though a single increment, such as 0111 to 1000, can flip many bits.

Find the complexity of recursive Fibonacci hard

Hint

Draw the call tree for fib(5). How many calls does each level produce?

Show solution

fib(n) calls fib(n-1) and fib(n-2), so the number of calls roughly multiplies by about 1.6 each level, which is O(2^n) as a simple upper bound (tight bound about 1.618^n). The tree recomputes the same values again and again. Memoizing each fib(k) once reduces the work to O(n) time and O(n) space, which is the idea behind dynamic programming.

Interview questions

  1. What does O(n log n) mean in plain words? Work grows a bit faster than linear: for each of n items you do about log n work, typical of divide-and-conquer such as merge sort.
  2. Why do we drop constants? For large n growth rate dominates, and constants depend on hardware and language. They still matter when comparing two algorithms of the same class.
  3. Time and space: which do you optimize? Ask about constraints. Often you trade one for the other (hash set versus sort).
  4. What is amortized O(1)? An average over a sequence of operations that guarantees constant cost per operation even though single operations may be expensive.

Interviewers look for: stating the complexity of both time and space without being asked, naming the input variables, and distinguishing average from worst case.

Quick check

An algorithm takes 1 second for n = 1,000. If it is O(n^2), roughly how long for n = 10,000?

Finished this lesson?

Further resources

Related lessons