Performance

Big O notation, without the maths

Short answer: Big O describes how the work grows when the input grows. O(n) means the work doubles when the input doubles; O(n²) means it quadruples. It is a shape, not a stopwatch.

Why you cannot just time it

Timing a program tells you about this machine on this run. Big O tells you what happens at 10x the input, on any machine. Compare two ways to add up 1..n:

#include <iostream>
using namespace std;

int main() {
    int n = 10;

    // way 1: a loop — n additions
    int a = 0;
    for (int i = 1; i <= n; i++) a += i;

    // way 2: the closed form — always 1 multiply
    int b = n * (n + 1) / 2;

    cout << a << " " << b << endl;
    return 0;
}

Same answer, wildly different growth. Way 1 is O(n); way 2 is O(1) — constant, no matter how large n gets.

The four shapes you will actually meet

Big O	Name	If n goes 10×	Typical cause
O(1)	constant	same	arithmetic, array index
O(log n)	logarithmic	+ a little	halving the range
O(n)	linear	10×	one pass over the data
O(n²)	quadratic	100×	a loop inside a loop

Count the work, don't time it

The trick is to count operations as a function of n. A single loop does n of them:

#include <iostream>
using namespace std;

int main() {
    int n = 8;
    int steps = 0;
    for (int i = 0; i < n; i++) {
        steps++;            // one unit of work per pass
    }
    cout << "n = " << n << ", steps = " << steps << endl;
    return 0;
}

Now nest it. The inner loop runs n times for each of the n outer passes:

#include <iostream>
using namespace std;

int main() {
    int n = 8;
    int steps = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            steps++;
        }
    }
    cout << "n = " << n << ", steps = " << steps << " = n*n" << endl;
    return 0;
}

Change n to 4 and 16 in the code: the step count goes 16 → 256. That is quadratic growth, and it is why a nested loop over 100,000 items is a problem.

Logarithmic: halving

Each pass throws away half the remaining range, so the count grows like log₂(n):

#include <iostream>
using namespace std;

int main() {
    int n = 1000000;
    int steps = 0;
    while (n > 1) {
        n /= 2;
        steps++;
    }
    cout << "steps to shrink 1000000 to 1: " << steps << endl;
    return 0;
}

20 steps for a million. This is why binary search is fast, and why the √n prime check beats trial division.

Drop the constants, keep the shape

O(2n) is written O(n); O(n² + n) is written O(n²). Constants and smaller terms disappear because at large n the biggest term dominates. So two loops one after another is O(n), not O(n²):

#include <iostream>
using namespace std;

int main() {
    int n = 8;
    int steps = 0;
    for (int i = 0; i < n; i++) steps++;     // n
    for (int i = 0; i < n; i++) steps++;     // + n
    cout << "two separate loops: " << steps << " = 2n, which is O(n)" << endl;
    return 0;
}

What this changes in your own code

Nested loops over the same data are the usual O(n²) culprit — see Two-Sum Exists and compare it with what a sorted array would allow.
Halving is a superpower. Any time you can discard half the candidates, you are in log territory.
Precomputing pays off. Range Sum Queries turns O(n) per question into O(1) after one O(n) pass.

Interview follow-ups

What is the complexity of this loop? Count how many times the innermost statement runs as a function of n, then drop constants.
Why is O(n log n) the usual sorting bound? Because comparison sorting needs n log n comparisons in the worst case — better than the O(n²) of bubble sort.
Does Big O care about memory? Not this notation — space complexity is a separate Big O over memory. Counting sort trades space for time.

Related: compiler errors, vector vs array, and the practice section where every problem's deep-dive states its complexity.