Models of Computation and Cost

We happily say "this algorithm runs in O(n\log n)" — but steps of what? A step on a modern laptop, a tick of a Turing machine, a line of pseudocode, a machine instruction? Until you pin that down, "counting steps" is counting nothing in particular. Before any analysis can mean something you must fix a model of computation (what the machine is) and a cost measure (what one step costs). Everything downstream — every asymptotic bound you will ever prove — is stated relative to that choice.

The good news: for almost all everyday algorithm analysis there is one standard, sensible choice — the RAM model with unit-cost operations on machine words — and it agrees with the Turing machine up to a polynomial. The bad news: the choice hides a landmine (arithmetic on huge numbers) that quietly breaks careless analyses. This page makes the model explicit so your step-counts finally mean something.

The random-access machine (RAM)

The RAM is the idealised stand-in for a real computer that we actually analyse algorithms on. It has:

an unbounded array of memory cells, each holding an integer, addressed by index — reading or writing M[i] takes one step (random access: cell 1000000 is as cheap as cell 0);
a fixed set of primitive operations — load, store, add, subtract, multiply, compare, conditional jump — each costing one step;
a program of finitely many instructions executed one after another.

This is deliberately close to how you already think about code: array indexing is O(1), an arithmetic operation is O(1), and the running time is just the number of primitive operations executed. The RAM's superpower over the Turing machine is exactly that constant-time random access — a Turing machine must shuffle its head along the tape to reach a distant cell, which is why some tasks look slower on it.

What legitimately counts as one operation?

The whole model lives or dies on this question. The honest answer: an operation is unit-cost only when it acts on a bounded amount of data — one machine word. Here is the count made explicit on a tiny routine:

function sumArray(a: number[]): number { let total = 0; // 1 op: store for (let i = 0; i < a.length; i++) { // i<n test + i++ each iteration total = total + a[i]; // 1 load (a[i]) + 1 add + 1 store, per iteration } return total; // 1 op } // n iterations x (a few unit-cost ops) + constant setup = Theta(n)

Every line touches a fixed number of words, so each is O(1), the loop body runs n times, and the total is \Theta(n). That is the entire discipline of RAM analysis: identify the primitive operations, check each is genuinely constant-work, and count how often the loops run them.

Unit cost vs logarithmic cost

There are two ways to charge for an operation, and they only agree when numbers stay small.

Cost measure	Charge for one operation	When it's the right model
Unit-cost	Exactly 1, regardless of how big the numbers are.	Numbers fit in a machine word — the everyday assumption.
Logarithmic-cost	\Theta(\text{bits}): an operation on a value v costs \Theta(\log v) (its number of digits).	Numbers can grow without bound — cryptography, big-integer arithmetic.

Unit-cost is the convenient fiction; logarithmic-cost is the honest reckoning that a 4096-bit multiply really does more work than an 8-bit one. The resolution most of computer science adopts is the word-RAM: fix a word size of w bits, assume every value fits in a word, and then unit-cost is legitimate because each operation touches only w bits — a constant. The usual convention ties w to the input size, w = \Theta(\log n), big enough to index all n inputs and hold a pointer, and no bigger.

To even address an array of n elements you need indices up to n, and an index that large needs \log_2 n bits. If a single word couldn't hold an index, "constant-time array access" would be a lie — you'd need several words just to name the cell. So w \ge \log_2 n is the minimum for the model to be coherent. Setting w = \Theta(\log n) makes it exactly big enough and no larger, which is why on a real 64-bit machine you can pretend words are unit-cost right up until your data set approaches 2^{64} elements — a boundary you will physically never reach.

Turing machines, RAMs, and polynomial equivalence

If the RAM is so much friendlier, why does theory keep the clunky Turing machine around? Because we need a robust definition of "efficient", and robustness comes from the models agreeing. They do — not exactly, but up to a polynomial:

A Turing machine running in time T(n) can be simulated by a RAM in time O(T(n)) — the RAM is at least as fast.
A (word-)RAM running in time T(n) can be simulated by a Turing machine in time O(T(n)^k) for a small fixed k — a polynomial slowdown, not an exponential one.

The upshot is the reason the class \mathbf{P} of polynomial-time problems is so stable: "solvable in polynomial time" means the same thing on a Turing machine, a RAM, your laptop, or any reasonable model, because a polynomial of a polynomial is still a polynomial. This is the extended (or strong) Church–Turing thesis: every physically reasonable model of computation can simulate every other with only polynomial overhead. It is what lets us analyse on the comfortable RAM yet quote results about \mathbf{P} with a straight face. (Quantum computing is the famous candidate exception to the extended thesis — but that is a story for another course.)

The single most common cost-model blunder: treating any single arithmetic operation as constant time even when the numbers grow with n. Consider computing 2^n by repeated squaring, or a Fibonacci number F_n. The value has about n bits, so the final additions and multiplications each move \Theta(n) bits — they are not unit-cost at all, and an analysis that charges them O(1) undercounts the real work by a factor of n. Unit-cost is a promise you make only while values fit in a machine word. The moment a quantity can exceed 2^w — factorials, exact powers, cryptographic keys, arbitrary-precision rationals — switch to the logarithmic (bit-complexity) measure and charge \Theta(\text{number of bits}) per operation, or your bound is simply wrong.