Introduction to Algorithm Analysis

Introduction to Algorithm Analysis

Two programmers hand you two correct solutions to the same problem. Which is better? Timing them with a stopwatch is a lie waiting to happen: the result depends on the CPU, the compiler, the language, and the one input you happened to test — run it on a faster machine and the loser wins. Algorithm analysis escapes that noise by counting the work an algorithm does as a function of input size n, so the answer survives every change of hardware and language.

But "count the work" hides a question this page exists to answer: count it against what machine? You cannot count operations without first agreeing what one operation costs. That agreement is a cost model, and every Big-O you will ever write is implicitly a statement about one specific model. Get the model right and analysis predicts reality; forget the model's assumptions and it will confidently mislead you.

The RAM cost model — the machine Big-O secretly assumes

Nearly all complexity analysis is done on the Random Access Machine (RAM) model. Its three assumptions are what make a bound like O(n) meaningful:

• Unit-cost operations. Each primitive step — an arithmetic op, a comparison, an assignment, a memory read/write — costs 1, regardless of the values involved.
• Uniform memory access. Reading a[0] costs the same as reading a[1000000]. Memory is a flat array with constant-time random access — this is the "RA" in RAM.
• Sequential execution, word-sized data. One instruction at a time, and each machine word (an integer, a pointer) fits in O(1) space and is manipulated in O(1) time.

Under these rules, counting operations is well-defined, and we then summarize the count by its asymptotic growth — dropping constants and low-order terms. The formal machinery for that summary (the ∃c,n0 definition of O, plus Ω and Θ) is developed on Big-O Notation; the technique for deriving a count from real code lives on Understanding Time Complexity. This page is about the assumptions underneath all of that.

Where the model lies — and what to use instead

The RAM model is an abstraction, and every one of its three assumptions can break. When it does, a lower Big-O can be the slower program.

1. Uniform memory access is false — the cache hierarchy. Real memory is a pyramid: an L1 hit costs ~1 ns, a main-memory (DRAM) access costs ~100 ns — a ~100× gap the RAM model charges as identical (both "1"). Consider summing every element of an n×n integer matrix stored row-major. Row-major traversal and column-major traversal visit exactly the same n² elements — identical RAM cost, both O(n2). Yet column-major strides across memory by a full row each step, missing cache on nearly every access; for a large matrix (say 10000×10000) this is commonly 3–10× slower when measured, despite the models being equal. The honest cost model here is the external-memory / cache-aware (DAM) model, which counts block transfers between cache levels, not individual operations.

2. Sequential access to disk is not random access — the I/O model. When data does not fit in RAM (databases, big files), the dominant cost is disk block transfers, not CPU ops. This is exactly why databases index with B-trees (high fan-out, few disk seeks) rather than binary search trees, even though both are O(log n) in the RAM model: a BST does ~log2n random seeks while a B-tree of order 100 does ~log100n — the same asymptotic class, but a ~6.6× reduction in the operation that actually costs money.

3. Unit-cost arithmetic breaks for big numbers. Multiplying two k-digit integers is not O(1) once k exceeds a machine word — it is O(k2) schoolbook, and this is why cryptographic and arbitrary-precision code cannot assume "arithmetic is free."

The judgment call: when to trust the model, when to profile

The RAM model is not "wrong" — it is a deliberate, extraordinarily useful lie. Its verdict on growth class is almost always right: an O(n log n) sort beats an O(n2) one at scale no matter what the cache does, because the cache changes the constant, not the class. The rule that follows:

• Use the RAM model to choose the growth class — it is cheap, hardware-independent, and decides the question that matters most (will this survive 10× the data?).
• Switch cost models when the constant is the story: tight numeric loops (cache model), out-of-core / database work (I/O model, count block transfers), big-integer or crypto code (bit-complexity, not word-complexity), and GPU/parallel work (the RAM model's "sequential" assumption is gone entirely).
• Then measure. Once two candidates are in the same class, only a profiler on real data can rank them — the tools and the constant-factor crossover are covered on Measuring Efficiency.

The trap this page inoculates you against: quoting a Big-O as if it were a promise about seconds. It is a promise about growth under a stated cost model — know the model, and you know exactly when the promise holds.

Key takeaways

• Algorithm analysis measures how work grows with input size, not wall-clock seconds — but only relative to a cost model.
• The default is the RAM model: unit-cost operations, uniform (flat) memory access, sequential word-sized execution. Every unqualified Big-O assumes it.
• The model lies when its assumptions break: the cache hierarchy (~100× L1-vs-DRAM gap), disk I/O (B-trees over BSTs for the same O(log n)), and big-number arithmetic (multiplication is not O(1)).
• Trust the RAM model to pick the growth class; switch models — and then profile — when the constant is what decides the winner.