Time & Space Complexity

How do you compare two algorithms? Timing them with a stopwatch depends on the computer, the compiler and the input. Instead we count how the number of basic steps grows with the input size n. That growth rate is the algorithm's time complexity.

#Big-O notation

O(f(n)) describes an upper bound on growth, ignoring constants and smaller terms:

• 3n² + 5n + 100 → O(n²) (n² dominates for large n)
• 7n + 20 → O(n)
• 500 → O(1)

We drop constants because we care about scaling: does doubling the input double the work, quadruple it, or barely change it?

#The growth rates you must know

Drag the slider to feel the difference:

#Analysing code

Count how many times the innermost statement runs.

// O(1): no loops depending on n
int first = a[0];

// O(n): one loop over n elements
for (int i = 0; i < n; i++) sum += a[i];

// O(n^2): a loop inside a loop, both over n
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) count++;

// O(log n): i doubles each time, so it reaches n after log2(n) steps
for (int i = 1; i < n; i *= 2) steps++;

// O(n log n): an O(log n) loop inside an O(n) loop
for (int i = 0; i < n; i++)
    for (int j = 1; j < n; j *= 2) work++;

You can check the counting by running it:

#include <stdio.h>

int main(void) {
    int sizes[] = {10, 100, 1000};
    for (int s = 0; s < 3; s++) {
        int n = sizes[s];
        long linear = 0, quad = 0, logn = 0, tri = 0;
        for (int i = 0; i < n; i++) linear++;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) quad++;
        for (int i = 1; i < n; i *= 2) logn++;
        for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) tri++;   // still O(n^2): n(n-1)/2
        printf("n=%4d  log:%2ld  linear:%5ld  triangle:%7ld  square:%8ld\n", n, logn, linear, tri, quad);
    }
    return 0;
}

n=  10  log: 4  linear:   10  triangle:     45  square:     100
n= 100  log: 7  linear:  100  triangle:   4950  square:   10000
n=1000  log:10  linear: 1000  triangle: 499500  square: 1000000

The "triangle" loop does n(n−1)/2 steps — about half of n², but still O(n²), because constants are dropped.

#Rules of thumb

1. Sequential steps add: O(n) followed by O(n²) is O(n + n²) = O(n²).
2. Nested loops multiply: an O(n) loop inside an O(n) loop is O(n²).
3. Drop constants and lower terms: O(2n + 10) = O(n).
4. Halving or doubling the remaining work each step gives O(log n).
5. Different inputs keep different letters: looping over n items then m items is O(n + m), not O(n).

#Best, average and worst case

The same algorithm can take different time on different inputs of the same size. For linear search on n items:

• Best case: the key is first — 1 comparison, O(1).
• Worst case: the key is last or absent — n comparisons, O(n).
• Average case: about n/2 comparisons — still O(n).

We usually quote the worst case, because it is a guarantee.

#Space complexity

Space complexity measures extra memory used as n grows. Reversing an array in place uses O(1) extra space; copying it into a new array uses O(n). A recursive function uses stack space proportional to its maximum recursion depth.