Big-O: How Fast Is My Code?

Counting steps, not seconds

Different computers run at different speeds, so we don't measure code in seconds. We ask: if the input gets bigger, how many more steps does my code take? The answer is written in Big-O notation. n is the size of the input, like the length of a vector.

Think of it like this: Finding a friend in your phone contacts by scrolling from the top takes longer with more contacts (it grows with n). Typing the first letters jumps there almost instantly.

O(1), O(n) and O(n²)

#include <iostream>
using namespace std;

long long linearSteps(int n) {          // one loop: O(n)
    long long steps = 0;
    for (int i = 0; i < n; i++) steps++;
    return steps;
}

long long quadraticSteps(int n) {       // loop inside a loop: O(n^2)
    long long steps = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) steps++;
    return steps;
}

int main() {
    for (int n : {10, 20, 40}) {
        cout << "n=" << n << "  O(1): 1  O(n): " << linearSteps(n)
             << "  O(n^2): " << quadraticSteps(n) << endl;
    }
    return 0;
}

Output

n=10  O(1): 1  O(n): 10  O(n^2): 100
n=20  O(1): 1  O(n): 20  O(n^2): 400
n=40  O(1): 1  O(n): 40  O(n^2): 1600

Double n and the O(n) work doubles, but the O(n²) work becomes four times bigger.

O(log n): halving

When each step throws away half of what's left, even huge inputs need very few steps:

#include <iostream>
using namespace std;

int halvings(long long n) {
    int steps = 0;
    while (n > 1) {
        n /= 2;
        steps++;
    }
    return steps;
}

int main() {
    for (long long n : {8LL, 1000LL, 1000000LL, 1000000000LL}) {
        cout << n << " -> " << halvings(n) << " steps" << endl;
    }
    return 0;
}

Output

8 -> 3 steps
1000 -> 9 steps
1000000 -> 19 steps
1000000000 -> 29 steps

A billion items need only about 30 halvings. Binary search (Module 6) works this way.

The Big-O cheat sheet

Remember: Big-O keeps only the fastest-growing part and drops plain numbers: 3n + 5 is O(n), and n² + n is O(n²).