Big-O and algorithm analysis

You now know how data is laid out in memory. The next question every data structure and algorithm choice comes down to is: how does the cost of an operation grow as the input grows? That’s what Big-O notation answers. It’s not about “is this fast on my laptop today” — it’s about “what happens when the input is 10x, 100x, 1,000,000x bigger.”

Why we don’t just measure in seconds

Timing code gives you a number that depends on your CPU, your language, background processes, and the specific input you tested. None of that generalizes. What does generalize is: as n (the input size) grows, how many extra operations does the algorithm need?

Big-O describes this relationship as a function of n, ignoring constant factors and lower-order terms, because those get dominated as n grows large enough.

def sum_array(arr):          # n = len(arr)
    total = 0                # 1 operation
    for x in arr:             # runs n times
        total += x            # 1 operation, n times
    return total              # 1 operation

# Total operations ≈ 1 + n + 1 = n + 2
# As n grows, the "+2" becomes irrelevant. We say this is O(n).

The growth curves that matter

These seven complexity classes cover almost everything you’ll encounter. The plot below shows how the number of operations grows as n grows from 1 to 20 — notice how quickly the curves separate.

Reading complexity off your code

You rarely need to derive Big-O from a formal proof — you can read it directly from control flow:

flowchart TD
  A["Single loop over n items"] --> A1["O(n)"]
  B["Nested loop: outer n, inner n"] --> B1["O(n²)"]
  C["Loop where index doubles/halves each time
(i *= 2 or i /= 2)"] --> C1["O(log n)"]
  D["Loop over n, and inside it a
log n operation (e.g. binary search)"] --> D1["O(n log n)"]
  E["Two separate loops, one after another,
both over n"] --> E1["O(n) + O(n) = O(n)
(constants drop, not O(n²))"]
  F["Recursion that branches into 2
calls per level, depth n"] --> F1["O(2ⁿ)"]

# O(n) — one loop
for x in arr:
    print(x)

# O(n²) — nested loop over the same input
for i in arr:
    for j in arr:
        print(i, j)

# O(n log n) — loop with a halving/doubling step inside
for x in arr:              # n times
    binary_search(arr, x)  # log n each

# O(log n) — the loop variable itself halves or doubles
i = 1
while i < n:
    i *= 2

# O(n) — NOT O(n²): sequential, not nested
for x in arr:      # n
    print(x)
for y in arr:      # n
    print(y)
# Total: n + n = 2n → drop the constant → O(n)

Common mistake: two sequential loops over the same array are O(n), not O(n²) — only nested loops multiply.

Big-O, Big-Ω, and Big-Θ

Big-O is technically an upper bound — “this algorithm never does more than this many operations.” But in casual use, people usually mean the tight bound. Formally there are three related notations:

• O (Big-O) — worst case / upper bound: “at most this much”
• Ω (Big-Omega) — best case / lower bound: “at least this much”
• Θ (Big-Theta) — tight bound: “exactly this, both upper and lower” — used when best and worst case have the same order of growth

Example: linear search

def linear_search(arr, target):
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

• Best case: target is the first element → Ω(1)
• Worst case: target is last or missing → O(n)
• Since best and worst differ, we don’t call this Θ(n) — we say “O(n) worst case” and separately note the best case.

Example: checking if an array is sorted

def is_sorted(arr):
    for i in range(len(arr) - 1):
        if arr[i] > arr[i+1]:
            return False   # can exit early
    return True

Best case (already sorted… wait, actually it must check every adjacent pair to confirm) is Θ(n) either way, since even the best case must scan the whole array to confirm sortedness — only the “found a violation” path can exit early.

Average case matters too — quicksort is O(n²) worst case but O(n log n) average case, which is why it’s still widely used (with randomized pivots to make the worst case astronomically unlikely).

Space complexity

Big-O also measures memory, not just time. Ask: how much extra memory does the algorithm use beyond the input itself?

def sum_array(arr):        # O(1) space — just one extra variable
    total = 0
    for x in arr:
        total += x
    return total

def double_all(arr):       # O(n) space — new array of size n
    return [x * 2 for x in arr]

def double_in_place(arr):  # O(1) space — modifies input, no new array
    for i in range(len(arr)):
        arr[i] *= 2
    return arr

There’s often a genuine time/space tradeoff: using a hash set to check duplicates is O(n) time but O(n) space; sorting first to check duplicates is O(n log n) time but O(1) extra space. Neither is universally “better” — it depends on your constraints.

Amortized analysis: when “sometimes slow” is actually fine

Some operations are usually cheap but occasionally expensive — and the average over many calls is still cheap. The classic example is appending to a dynamic array (covered in depth in the next two posts): most appends are O(1), but every so often the array must resize (allocate new memory, copy everything over), which is O(n) for that one call.

Why doubling (not adding a fixed amount) matters: if you grew the array by a fixed size (say, +10 each time) instead of doubling, resizes would happen every 10 appends forever, and the total cost over n appends becomes O(n²) — because you keep re-copying an array whose size grows linearly while resize frequency stays constant. Doubling means resize frequency shrinks geometrically, keeping the total copying work at O(n) across n appends, i.e., O(1) amortized per append.

# Amortized O(1) append — this is what list.append() does internally
class SimpleDynamicArray:
    def __init__(self):
        self._capacity = 1
        self._size = 0
        self._data = [None] * self._capacity

    def append(self, value):
        if self._size == self._capacity:
            self._resize(self._capacity * 2)  # the occasional O(n) step
        self._data[self._size] = value
        self._size += 1

    def _resize(self, new_capacity):
        new_data = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]  # O(n) copy — but rare
        self._data = new_data
        self._capacity = new_capacity

Key takeaways

1. Big-O measures growth, not speed. It tells you what happens as n gets large, ignoring constants and machine-specific timing.
2. Nested loops multiply, sequential loops add (and adding drops to the larger term — two O(n) loops in a row are still O(n)).
3. O vs Ω vs Θ: worst case, best case, and tight bound — most casual usage of “Big-O” means worst case unless stated otherwise.
4. Space complexity matters as much as time — always ask “how much extra memory beyond the input?”
5. Amortized analysis explains why an operation that’s occasionally O(n) can still be O(1) “on average” — the dynamic array’s doubling strategy is the canonical example.
6. At n = 1,000,000, the difference between O(n log n) and O(n²) is the difference between milliseconds and days. This is why the rest of this series obsesses over picking the right data structure and algorithm.

Practice problems

• Two Sum (Easy) — compare an O(n²) brute force to an O(n) hash-map solution
• Contains Duplicate (Easy) — O(n log n) sort vs O(n) hash set, a direct time/space tradeoff
• Sqrt(x) (Easy) — O(log n) binary search vs O(n) linear scan

What’s next

• Bits, bytes, and bitwise tricks — the O(1) operations your CPU does natively, and the tricks built on them
• Arrays: fixed-size and indexing — putting the O(1) access formula from the memory post into practice