JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Reading the Running Time Off the Code

You have met Big-O, Omega, Theta, and the growth zoo; now turn them into a habit — a small set of rules that lets you glance at a loop nest and call its running time on sight.

From notation to a reading habit

The earlier guides in this rung built the vocabulary: why we drop constants and low-order terms, Big-O as a ceiling, Theta as a tight verdict, and the growth zoo from constant up to factorial. This last guide spends them. The goal is a reliable habit: you look at a chunk of pseudocode, you count how often the real work happens as a function of n, and you name the growth — usually without writing a single line of algebra.

The whole method rests on one accounting rule from the very first rung: under the RAM model, each basic step — an arithmetic operation, a comparison, an array access — costs a bounded amount of time. So the running time, up to a constant factor, is just the total number of basic steps executed. Reading running time therefore reduces to counting: how many times does the body run, and how much bounded work does each run do? Get the count, attach Theta, and you are done.

Two rules: add for sequence, multiply for nesting

Almost everything follows from the sum and product rules. The sum rule: when two pieces of code run one after the other, their costs add, and a sum of growths collapses to the larger one — Theta(n) followed by Theta(n^2) is Theta(n^2), because the smaller term is exactly the low-order dust we agreed to discard. The product rule: when one loop is nested inside another, the inner cost runs once per outer iteration, so the costs multiply — an outer loop of n iterations wrapping an inner Theta(n) loop is Theta(n * n) = Theta(n^2).

These two rules let you tear a program into pieces, name each piece, and reassemble. Three separate single loops over an n-element array, run in sequence? Theta(n) + Theta(n) + Theta(n) = Theta(n). A doubly nested loop right after a single loop? Theta(n) + Theta(n^2) = Theta(n^2). The sum rule keeps you from over-counting cheap setup code; the product rule is where the exponents in n^2, n^3, and beyond actually come from. Master these two and most everyday code reads itself.

When the inner range moves: triangular loops

The most common trap in nested-loop analysis is the triangular loop, where the inner loop starts at the outer index instead of at zero. A naive reading says "outer n, inner n, so n^2" — and it happens to land in the right class, but for the wrong reason, and the same sloppiness will betray you elsewhere. The honest move is to write down the iteration count as a sum and evaluate it.

for i = 1 to n:
    for j = i to n:
        do_constant_work()

# inner runs (n - i + 1) times for each i
# total = sum from i=1 to n of (n - i + 1)
#       = n + (n-1) + ... + 1 = n(n+1)/2
A triangular loop: the body fires n(n+1)/2 times, which is Theta(n^2) even though it is only about half of a full n-by-n nest.

The sum n(n+1)/2 equals n^2/2 + n/2. Its leading term is n^2/2, so the whole thing is Theta(n^2): the constant 1/2 and the low-order n/2 are precisely the parts asymptotics throws away. This is worth internalising, because it explains why so many "all pairs" patterns — comparing every element with every later element, filling the upper triangle of a table — are quadratic even though each does only half the work of a square. Half of n^2 is still Theta(n^2); a constant factor never moves you to a smaller class.

Loops that multiply or divide the counter

Not every loop adds one to its counter. When a loop variable is doubled each pass — i = 1, 2, 4, 8, ... up to n — the number of iterations is not n but the number of doublings needed to reach n, which is about log base 2 of n. The same logarithm appears when a loop halves its range each pass, as in the halving step of binary search: a range of n becomes n/2, then n/4, and reaches size 1 after roughly log n steps. Whenever the counter is scaled by a constant factor rather than shifted by a constant, reach for a log.

Now combine this with the product rule and you can read the famous shapes. An outer loop running n times, each turn doing a binary-search-style Theta(log n) probe, is Theta(n) * Theta(log n) = Theta(n log n) — the linearithmic class that good sorting lives in. An outer loop over n with an inner doubling loop is likewise Theta(n log n). And a loop that doubles inside a loop that doubles is Theta(log n) * Theta(log n) = Theta((log n)^2). The exponents and the logs are not magic; they are just the sum and product rules applied to whatever the counter is doing.

A four-step reading routine

Here is the routine that ties it together. It works for the loop-based code you meet first; recursive code hands its count to a recurrence instead, which the divide-and-conquer rung handles. Two warnings to carry through every step: decide first which input you are analysing — typically the worst case, since that is the guarantee — and make sure the work inside the body really is bounded, because a hidden sort or a string copy inside the loop quietly multiplies the cost.

  1. Find the innermost real work and confirm one execution of it costs a bounded number of basic steps (no hidden inner loop, sort, or copy).
  2. Count how many times that work runs as a function of n — add the counter (linear), scale it (logarithmic), or write a sum when an inner range depends on an outer index.
  3. Combine pieces with the two rules: add costs for code in sequence (keep only the largest term), multiply costs for nested loops.
  4. Name the resulting growth and place it in the hierarchy; if the upper and lower counts meet, state a Theta, otherwise report O and Omega honestly.

Run this on a worked example. To find the closest pair among n points by checking every pair, the outer loop fixes one point (n choices) and the inner loop scans the later points (a triangular range), giving n(n+1)/2 distance computations, each a bounded handful of multiplications and a comparison. The body is bounded, the count is Theta(n^2), nothing runs in sequence to dominate it, so the brute-force routine is Theta(n^2). Notice we never timed anything — we read the class straight off the structure.

What the reading does and does not promise

Be clear about which input the count describes. A loop with an early exit — a linear search that stops on the first match — runs Omega(1) in the best case and Theta(n) in the worst, so a single Theta is wrong for it; you report the worst case as the guarantee, or analyse the average over an assumed input distribution and label it as such. Average-case time is only as trustworthy as the distribution you assumed, so never quote an average without saying what you averaged over.

And remember what the class hides. A Theta tag is a statement about scaling, not a verdict at every size: it only governs once n passes the threshold n0, so the hidden constants and low-order terms you discarded can make a Theta(n log n) routine genuinely lose to a Theta(n^2) one on small inputs. That is exactly why production sort routines fall back to insertion sort for tiny subarrays. The reading you just learned tells you which algorithm wins as inputs grow without bound — a real and central thing — but it deliberately stays silent about the crossover point, and you should too unless you measure.