Big-O without hand-waving

The question Big-O answers

Not "how fast is this program?" - that depends on the machine. The question is: if I double the input, what happens to the running time?

That question has a machine-independent answer, and it is the only thing that matters once your input is large.

Count operations, then throw things away

int sum_all(const int a[], int n) {
    int total = 0;              // 1 operation
    for (int i = 0; i < n; i++) // n+1 comparisons, n increments
        total += a[i];          // n additions
    return total;               // 1 operation
}

Total: roughly 3n + 3 operations. We then do two things.

Drop the constant term. For n = 1,000,000, the +3 is irrelevant.

Drop the multiplier. 3n and 100n both double when n doubles. The multiplier depends on your CPU and compiler; the shape does not.

What is left is n. We write O(n) and say the function is linear.

Reading a loop

for (int i = 0; i < n; i++)              // O(n)
    for (int j = 0; j < n; j++)          // O(n) each time
        cout << i * j << " ";            // O(1)

Nested loops multiply: O(n) x O(n) = O(n^2).

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        cout << a[i] << a[j] << "\n";

This one looks cheaper, and it is - but only by a constant. The inner loop runs n-1, then n-2, down to 0. The total is n(n-1)/2, which is n^2/2 - n/2. Drop the constant and the lower term: still O(n^2). Half of a huge number is still huge.

for (int i = 1; i < n; i = i * 2)
    cout << i << " ";

i goes 1, 2, 4, 8, ... The loop runs until 2^k is at least n, so k = log2(n). This is O(log n). Any time a variable is multiplied or divided instead of incremented, you have a logarithm.

The table you should memorise

Operations performed, for each growth rate:

A modern CPU does roughly 10^8 to 10^9 simple operations per second. Put that against the table:

• O(n^2) at n = 100,000 is 10^10 operations: about a minute or more.
• O(n log n) at the same n is 1.7 million: instant.
• O(2^n) at n = 100 is more operations than there are atoms in the observable

universe. No faster computer will save you. Only a better algorithm will.

Big-O, Big-Omega, Big-Theta

These get confused constantly, and the difference is one mark.

• O(f) is an upper bound. "No worse than."
• Omega(f) is a lower bound. "No better than."
• Theta(f) is both. "Exactly this growth."

Linear search is O(n) and Omega(1) - one comparison if the item is first, n if it is last. It is not Theta of anything single, so we usually state the worst case, O(n).

Technically, saying merge sort is O(n^2) is true - it is an upper bound, just a loose one. In an exam, always give the tightest bound you can.

Best, average, worst

Quick sort's worst case is O(n^2) and hash lookup's worst case is O(n), yet both are used everywhere - because the bad cases are rare and avoidable in practice. Knowing when the worst case happens is the real skill, and the next few lessons cover exactly that.

Space complexity

The same notation applies to memory.

int count_pairs(const int a[], int n) {
    int c = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] + a[j] == 0) c++;
    return c;
}

Time O(n^2), space O(1) - it uses three variables no matter how big n is.

Merge sort is O(n log n) time but O(n) extra space, because it needs a temporary array. Quick sort is in-place, O(log n) space for the recursion stack. On a memory-limited system that difference decides which one you use.