What Big-O Notation Actually Means

Big-O notation is one of those things that gets explained a hundred different ways, and half of them are subtly wrong. So here's what it actually is, stripped of the hand-waving.

Big-O Is About Growth, Not Speed

This is the single most common misconception. Big-O does not tell you how fast your code runs. It tells you how the runtime grows as the input size increases.

An O(n) algorithm with a constant factor of 1000 is slower than an O(n^2) algorithm for inputs under ~1000 elements. Big-O only guarantees that eventually, as n gets large enough, the O(n) version wins. That "eventually" matters a lot in practice.

Formally, O(f(n)) means your algorithm's runtime is at most proportional to f(n) for sufficiently large n. It's an upper bound on growth rate. Not an exact measurement. Not an average. An upper bound.

The Common Complexity Classes

O(1) — Constant Time

The runtime doesn't depend on input size at all. Array index access, hash map lookup (amortized), pushing to the end of a dynamic array.

def get_first(arr):
    return arr[0]  # Always one operation, regardless of array size

A common mistake: "O(1) means one operation." No — it means a fixed number of operations. Could be 50 operations. As long as it doesn't change with n, it's O(1).

O(log n) — Logarithmic

You're cutting the problem in half each step. Binary search is the classic example. Balanced BST operations. The number of digits in a number.

For n = 1,000,000, log2(n) is about 20. That's absurdly efficient.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

O(n) — Linear

You look at every element once (or a fixed number of times). Finding the max in an unsorted array. Summing a list. Any single pass through the data.

def find_max(arr):
    result = arr[0]
    for x in arr:
        if x > result:
            result = x
    return result

O(n log n) — Linearithmic

This is the sweet spot for comparison-based sorting. Merge sort, quicksort (average case), heapsort. You can't sort faster than this with comparisons alone — that's a proven lower bound.

Also shows up in algorithms that do a linear scan for each level of a divide-and-conquer recursion.

O(n^2) — Quadratic

Nested loops over the same data. Bubble sort, selection sort, checking all pairs. The brute-force solution to "two sum" (before you think of using a hash map).

# Brute force two sum — O(n^2)
def two_sum_brute(arr, target):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == target:
                return [i, j]

For n = 10,000, that's 100 million operations. You'll feel the slowdown.

O(2^n) — Exponential

The problem doubles with each additional input element. Naive recursive Fibonacci. Generating all subsets. Brute-forcing the traveling salesman.

# Naive Fibonacci — O(2^n), don't actually do this
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

For n = 40, this takes over a billion calls. For n = 50, you'll be waiting a while.

Things People Get Wrong

"Drop the constants" doesn't mean constants don't matter. Big-O drops them because it's describing asymptotic behavior. In your actual code, an O(n) algorithm with 10x the constant factor of another O(n) algorithm is 10x slower. Profile your code, don't just count Big-O classes. Big-O is the worst case... sometimes. When someone says "quicksort is O(n log n)," they usually mean the average case. Worst case is O(n^2). When someone says "hash table lookup is O(1)," they mean amortized — worst case is O(n) due to collisions. Context matters. Ask which case is being described. Space complexity exists too. An algorithm that runs in O(n) time but uses O(n^2) space might be worse than one that runs in O(n^2) time with O(1) space, depending on your constraints. Don't ignore memory.

Why This Matters Beyond Interviews

In interviews, Big-O is how you justify your approach. "This runs in O(n log n) because we sort first, then do a linear scan" — that's the language interviewers expect.

In production, it's about predicting scaling behavior. Your endpoint handles 1,000 users fine today. What happens at 100,000? If your core algorithm is O(n^2), you've got a problem. If it's O(n log n), you're probably fine.

The real skill isn't memorizing which class each algorithm belongs to — it's being able to look at a piece of code and reason about how it scales. That takes practice. CodeUp has problems specifically designed to build this intuition, where you can test your solutions against increasingly large inputs and see the complexity differences firsthand.

Quick Reference

Complexity	Name	Example	n=1000 ops (approx)
O(1)	Constant	Hash lookup	1
O(log n)	Logarithmic	Binary search	10
O(n)	Linear	Array scan	1,000
O(n log n)	Linearithmic	Merge sort	10,000
O(n^2)	Quadratic	Nested loops	1,000,000
O(2^n)	Exponential	All subsets	Good luck

Get comfortable with these, and you'll be able to estimate the feasibility of any approach in seconds. That's the whole point.