Computational Complexity

How Algorithms Scale

Two algorithms can solve the same problem, yet one finishes instantly on data that would take the other centuries. Computational complexity measures how an algorithm's resource use — usually time (number of basic steps) — grows as the input size $n$ grows. It predicts scalability, the property that matters most as data gets large.

We describe growth with big-O notation, which captures the dominant term and ignores constants and lower-order terms — because for large $n$ only the fastest-growing part matters. Common complexity classes, from best to worst:

• $O(1)$ — constant: independent of $n$ (indexed array access).
• $O(\log n)$ — logarithmic: halving the problem each step (binary search).
• $O(n)$ — linear: one pass over the data (a single loop).
• $O(n \log n)$ — linearithmic: efficient sorting (merge sort).
• $O(n^2)$ — quadratic: nested loops over the data.
• $O(2^n)$ — exponential: doubling with each added element — infeasible beyond small $n$.

The gulf between classes is enormous. For $n = 1{,}000{,}000$, a linear algorithm does a million steps while a quadratic one does a trillion — the difference between a second and weeks. This is why choosing the right algorithm usually matters far more than the speed of the machine or micro-optimising the code.

Big-O describes asymptotic behaviour — the trend as $n \to \infty$ — deliberately dropping constants. So $O(n)$ and $O(100n)$ are the same class, because for large enough $n$ the algorithm that scales better wins regardless of constant factors. This focus on scaling, not exact step counts, is what makes complexity a clean and powerful predictor.

Common pitfall: confusing an algorithm's complexity class (how it scales) with its raw speed on small inputs. Big-O is about asymptotic growth as $n \to \infty$, so it drops constants — $O(n)$ beats $O(n^2)$ for large $n$ even if the quadratic one is faster on tiny inputs. A lower complexity class is not automatically faster on every input; it is guaranteed to win once $n$ is large enough, which is what scalability means.