Big-O and Complexity

Here is a question that sounds simple: which of two programs is faster? Timing them with a stopwatch feels like the obvious answer, but it is a trap. The same program runs at different speeds on a laptop and a server, on a busy machine and an idle one, compiled by different compilers, on Tuesday and on Thursday. Wall-clock time measures the machine as much as the algorithm. Computer science sidesteps the whole mess with one move: instead of measuring seconds, count steps, and instead of counting steps for one input, ask how the count grows as the input gets bigger. This is the opening move of MIT's introductory algorithms course, and it is the single most useful analytical habit in programming.

Think of it like comparing two recipes not by how long they took in your kitchen last night, but by how the effort scales with guests. One recipe needs one pot no matter how many people come. Another needs a separate pan per guest. A third has you introduce every guest to every other guest. For four people the differences barely matter. For a thousand, they are everything. Algorithms behave exactly the same way, and the input size, written n, plays the role of the guest count.

The model: every basic operation costs one step

To count steps we need to agree on what a step is. The standard model, the one used throughout MIT's 6.006 course, says: any basic operation takes one unit. An addition, a comparison, reading a variable, storing a value, each costs 1. This is deliberately crude. A multiplication is not really the same cost as a comparison on physical silicon, but the crudeness is the point: it erases the machine from the analysis, and what survives is a property of the algorithm alone.

Two examples anchor the idea. Summing a list of n numbers takes about n additions: the work grows in a straight line with the input, twice the data means twice the steps. Checking whether the first element of a list is zero takes one comparison whether the list holds ten items or ten billion: the work does not grow at all. The first algorithm is linear, the second is constant, and no hardware upgrade will ever change which category either belongs to.

What big-O actually says

Big-O notation is the vocabulary for growth categories. Informally: a function f(n) is O(g(n)) when, for all large enough inputs, f(n) stays at or below some fixed constant multiple of g(n). Formally, there exist a constant c greater than zero and a threshold n0 such that f(n) <= c * g(n) for every n >= n0. That definition, standard across 6.006 and the Open Data Structures textbook, has two quiet ideas built into it: we only care about large n (small inputs are fast under any algorithm), and we allow a constant factor of slack (because constants belong to the machine, not the algorithm).

Big-O is an upper bound: it says the growth is no worse than g(n). Its two siblings complete the family. Omega gives a lower bound, growth at least this fast, and Theta pins the growth exactly, both bounds at once. Everyday engineering speech says big-O for all three, which is usually harmless, but the distinction earns its keep later: when the sorting lesson says comparison sorting requires Omega of n log n comparisons, that is a claim no cleverness can beat, which is a very different statement from an upper bound.

The definition explains the two famous simplification rules. First, drop constant factors: 3n and 300n are both O(n), because the constant c absorbs the difference. Second, drop lower-order terms: 3n^2 + 50n + 7 is O(n^2), because once n is large the n^2 term drowns the rest. At n = 1000, the quadratic term contributes three million while everything else contributes about fifty thousand, and the gap only widens. What remains after both rules is the growth rate, the part of an algorithm's cost that follows it onto every machine it will ever run on.

One misconception is worth killing early: fewer lines of code does not mean faster code. A three-line program with a loop inside a loop can do millions of steps, while a twenty-line program that touches each item once does thousands. Big-O counts executed steps, not written lines, and the two are almost unrelated.

The ladder of growth rates

• O(1), constant: the same work regardless of input size. Reading an array slot by index, pushing onto a stack.
• O(log n), logarithmic: each step cuts the problem in half, so even a billion items need only about 30 steps. Binary search lives here.
• O(n), linear: touch everything once. Summing a list, scanning for a value.
• O(n log n), linearithmic: touch everything, about log n times over. The home of good sorting algorithms.
• O(n^2), quadratic: compare everything with everything. Nested loops over the same data, naive sorting.
• O(2^n), exponential: the work doubles every time n grows by one. Trying every subset. Fine at n = 20, impossible at n = 100.

The curves above are why the categories matter more than any constant factor. To make the gaps concrete, assume a machine doing a billion basic operations per second. At n equal to one million: a logarithmic algorithm finishes in about 20 nanoseconds, a linear one in a millisecond, an n log n one in about 20 milliseconds, and a quadratic one in roughly 17 minutes. Push n to a billion and the quadratic algorithm needs around 32 years while the linear one takes a second. Exponential growth is in a different universe entirely: 2^n at n = 60 is already about 36 years of work at a billion steps per second, and at n = 1000 the step count dwarfs the number of atoms in the observable universe. No conceivable hardware rescues an exponential algorithm; only a better algorithm does.

Why this matters for protected code

Complexity is the honest currency of this entire Academy. Obfuscation deliberately spends performance to buy analysis resistance, and every technique in Levels 5 and 6 has a growth-rate price tag: string decoding adds linear work per string, virtualization multiplies each operation by a constant dispatch cost, and the lesson on whether obfuscation slows code down is really a complexity discussion in disguise. The attack side is priced the same way. A defense that forces an attacker to do per-script work scales very differently from one they can break once and reuse, and you now own the vocabulary that makes that difference precise.

Measure algorithms by how their step count grows with input size, not by seconds on one machine. Big-O names the growth category, constants and small terms fall away, and the ladder runs O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n). The category, not the constant, decides what is feasible at scale.

Frequently asked questions