Algorithm Analysis & Big-O

How to predict how fast an algorithm runs without ever executing it.

Why analyze?

The intuition

If checking one item in a database takes 0.01 s, then:

100 items → 1 second ✅
10 000 items → 100 seconds 🤔
10 000 000 items → 28 hours ❌

So "fast enough" depends entirely on input size. We need a way to predict this without running the code on huge inputs.

There are two approaches:

Empirical analysis — implement, time it. Direct, but implementation-dependent and impractical for very large N.
Algorithm analysis — derive a formula T(N) describing the number of operations as a function of input size. Implementation-independent and lets you extrapolate.

The 5 rules for deriving T(N)

You apply these to the pseudocode, line by line:

Rule 1 — Simple statements take constant time

sum = N * (N+1) / 2;     // T(N) = constant — independent of N

Assignments, comparisons, arithmetic, prints — all count as 1.

Rule 2 — A for-loop multiplies

for (i = 1; i <= N; i++)
    sum = sum + i;       // T(N) = N

Rule 3 — Nested loops multiply sizes

for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        table[i][j] = i * j;   // T(N) = N · N = N²

Rule 4 — Sequential code adds

for (i = 0; i < N; i++) table[i] = i*i;   // N
sum = 0;
for (i = 0; i < N; i++) sum += table[i];  // N
                                          // total T(N) = 2N

Rule 5 — If/else takes the larger branch

if (number == 20) {
    for (i = 0; i < N; i++) sum += a[i];          // N
} else {
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++) b[i] = i*j;        // N²
}
// T(N) = max(N, N²) = N²

From T(N) to Big-O

Once you have T(N), two simplifications happen:

Keep only the dominant term (the one that grows fastest).
Drop multiplicative constants.

Why?

For large N, lower-order terms become negligible. 3N² + N + 10 at N=1000 is dominated entirely by the 3N² term. The constant 3 doesn't matter for telling apart algorithms whose growth rates differ — only their scaling matters.

T(N)	Dominant	Big-O
3N² + 5N	3N²	O(N²)
5N + 10	5N	O(N)
2N³ + 100N² + N + 7	2N³	O(N³)

Words of caution

Big-O is asymptotic — not the whole story

If you compare T(N) = 100N (= O(N)) with T(N) = N² (= O(N²)), the linear one is "better" — but only for N > 100. For smaller inputs, the quadratic one wins.

When two algorithms have the same Big-O, the one with the smaller constant factor is preferred.
For very small inputs, an asymptotically slower algorithm can outperform a faster one.

Worked example: Binary Search

Find a key in a sorted array. Each iteration discards half of the remaining search range.

Binary_Search(table, key):
    First = 0
    Last = N - 1
    while (First <= Last):
        Mid = (First + Last) / 2
        if (table[Mid] == key) return FOUND
        else if (key < table[Mid]) Last = Mid - 1
        else                        First = Mid + 1
    return NOT_FOUND

Trace with N = 8 (worst case)

Iteration	First	Last	Mid
1	0	7	3
2	4	7	5
3	6	7	6
4	7	7	7

4 iterations. Note log₂8 = 3, so T(N) = log(N) + 1 = O(log N).

The intuition behind log N

Every iteration halves the problem. If you have to halve N values down to 1, that takes log₂ N halvings. Doubling N adds just one extra step.

Standard complexity classes

Class	Big-O	Example	N=1000 ops
Constant	O(1)	Array access	1
Logarithmic	O(log N)	Binary search	~10
Linear	O(N)	Linear search	1 000
Log-linear	O(N log N)	Heapsort, mergesort	~10 000
Quadratic	O(N²)	Insertion sort, nested loops	1 000 000
Cubic	O(N³)	Matrix multiply (naive)	10⁹
Exponential	O(2ⁿ)	Brute-force TSP, subset enum.	>10³⁰⁰

Ordering: O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(N³) < O(2ⁿ)

Exam tips

What you'll likely be asked

"Derive T(N) for this pseudocode" — apply the 5 rules line by line.
"Give the Big-O" — keep the dominant term, drop constants.
"Estimate the time for input size X given time for size Y" — use the ratio: if T = O(N²) and N doubles, time grows by 4×.
"Which of these is faster?" — compare Big-O classes; if tied, look at constants.