Skip to content
LumenaryAcademy
Core 75 min

Measuring the cost of a program

Counting steps, growth rates, the precise meaning of O, Ω and Θ, and why appending to a list is cheap on average.

Code tested · 6AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

Two correct programs

A national examinations board has a million candidate records and must check that no two candidates were given the same ID. Here are two correct ways to do it in Python:

python
def has_duplicate_pairs(ids):
    n = len(ids)
    for i in range(n):
        for j in range(i + 1, n):
            if ids[i] == ids[j]:
                return True
    return False

def has_duplicate_set(ids):
    seen = set()
    for x in ids:
        if x in seen:
            return True
        seen.add(x)
    return False

Both are always right. But when there are no duplicates, the first compares every pair: n(n−1)/2n(n-1)/2 comparisons, about 5×10115 \times 10^{11} for n=106n = 10^6. Even at a hundred million comparisons a second that is well over an hour, and Python is slower. The second does one set lookup and one insertion per record and finishes in well under a second.

Correctness is not enough: an answer that arrives next week is, for most purposes, no answer. This lesson gives you the tools to predict a program's cost before running it, to compare algorithms independently of the machine, and to check predictions by experiment. Every later lesson uses them.

IntuitionH

Count steps, not seconds

Why not just time programs? Because seconds depend on the processor, the language, the Python version and what else the computer is doing, so a measurement on one laptop says little about a phone or a server.

Instead, we count steps: simple operations such as an arithmetic operation, a comparison, an assignment, reading xs[i], or calling a function. Each takes at most some fixed amount of time on a given machine, so if we know how the number of steps grows with the input, we know how the time grows, up to a constant factor that depends on the machine. This idealised machine, in which every simple operation costs one unit, is called the cost model (formally, a random-access machine, or RAM).

We then make two simplifications, both deliberate:

  1. We describe cost as a function of the input size nn: the length of a list, the number of records, the number of digits.
  2. We care about growth, not constants. The difference between 3n3n and 5n5n steps can be erased by a faster machine or a better compiler; the difference between nn and n2n^2 cannot, once nn is large.

Analogy, not a formal construction

To compare walking with driving for a long journey, you don't care that the driver spends a minute finding the car keys. What matters is how the journey time grows with distance: one hour per 5 km versus one hour per 80 km. The key-finding is a constant; the speed is the growth rate. Asymptotic analysis is the habit of ignoring the keys.

DefinitionsH

Running time and the three notations

Definition— running time

For an algorithm AA, let TA(x)T_A(x) be the number of steps AA takes on input xx. Its worst-case running time is T(n)=max⁡{TA(x):x has size n}T(n) = \max \{ T_A(x) : x \text{ has size } n \}, and its best-case running time is the corresponding minimum. Its average-case running time is the expected value of TA(x)T_A(x) when inputs of size nn are drawn from a stated probability distribution.

Running times are functions from input sizes to step counts. To compare such functions while ignoring constant factors and small inputs, we use three notations. Throughout, ff and gg are functions from the natural numbers to the non-negative reals.

Definition— O, Ω and Θ

  • f(n)=O(g(n))f(n) = O(g(n)) ("ff is big-O of gg") if there are constants c>0c > 0 and n0n_0 such that f(n)≤c g(n)f(n) \le c\, g(n) for all n≥n0n \ge n_0. It says ff grows at most as fast as gg.
  • f(n)=Ω(g(n))f(n) = \Omega(g(n)) ("big-Omega") if there are constants c>0c > 0 and n0n_0 such that f(n)≥c g(n)f(n) \ge c\, g(n) for all n≥n0n \ge n_0. It says ff grows at least as fast as gg.
  • f(n)=Θ(g(n))f(n) = \Theta(g(n)) ("big-Theta") if both hold: f(n)=O(g(n))f(n) = O(g(n)) and f(n)=Ω(g(n))f(n) = \Omega(g(n)). It says ff and gg grow at the same rate, up to constant factors.

The "=" here is a traditional abuse of notation: O(g)O(g) is really a set of functions, and f=O(g)f = O(g) means f∈O(g)f \in O(g). That is why we never write O(g)=fO(g) = f, and why n=O(n2)n = O(n^2) and n2=O(n2)n^2 = O(n^2) do not imply n=n2n = n^2.

Two more pieces of vocabulary are useful. We write f(n)=o(g(n))f(n) = o(g(n)) ("little-o") when f(n)/g(n)→0f(n)/g(n) \to 0: ff grows strictly slower than gg. And the definitions give a handy test:

Theorem— The limit test

Suppose lim⁡n→∞f(n)/g(n)=L\lim_{n \to \infty} f(n)/g(n) = L exists (possibly ∞\infty). If 0<L<∞0 < L < \infty, then f=Θ(g)f = \Theta(g). If L=0L = 0, then f=O(g)f = O(g) but f≠Ω(g)f \ne \Omega(g). If L=∞L = \infty, then f=Ω(g)f = \Omega(g) but f≠O(g)f \ne O(g).

Proof

If 0<L<∞0 < L < \infty, then by the definition of a limit there is an n0n_0 with L/2≤f(n)/g(n)≤2LL/2 \le f(n)/g(n) \le 2L for all n≥n0n \ge n_0, so c=2Lc = 2L witnesses OO and c=L/2c = L/2 witnesses Ω\Omega. If L=0L = 0, then f(n)/g(n)≤1f(n)/g(n) \le 1 for large nn, giving OO with c=1c = 1; and for any proposed c>0c > 0, eventually f(n)/g(n)<cf(n)/g(n) < c, so no cc can witness Ω\Omega. The case L=∞L = \infty is symmetric.

∎

Worked examplesH

Proving bounds

To prove an OO or Ω\Omega bound from the definition, you exhibit the constants. Any constants that work will do; there is no need to find the best ones.

Theorem— A quadratic

3n2+10n+7=Θ(n2)3n^2 + 10n + 7 = \Theta(n^2).

Proof

Upper bound: for n≥1n \ge 1 we have 10n≤10n210n \le 10n^2 and 7≤7n27 \le 7n^2, so 3n2+10n+7≤20n23n^2 + 10n + 7 \le 20 n^2. Take c=20c = 20, n0=1n_0 = 1. Lower bound: for all n≥0n \ge 0, 3n2+10n+7≥3n23n^2 + 10n + 7 \ge 3n^2. Take c=3c = 3, n0=0n_0 = 0.

∎

The same argument shows that any polynomial adnd+⋯+a1n+a0a_d n^d + \dots + a_1 n + a_0 with ad>0a_d > 0 is Θ(nd)\Theta(n^d): the leading term dominates, and the lower-order terms only affect the constants. This is why we write Θ(n2)\Theta(n^2) and not Θ(3n2+10n+7)\Theta(3n^2 + 10n + 7).

Theorem— Logarithm bases do not matter

For any constants a,b>1a, b > 1, log⁡an=Θ(log⁡bn)\log_a n = \Theta(\log_b n).

Proof

By the change-of-base formula, log⁡an=log⁡bnlog⁡ba\log_a n = \dfrac{\log_b n}{\log_b a}, and log⁡ba\log_b a is a positive constant. So log⁡an\log_a n is a constant multiple of log⁡bn\log_b n, which is Θ\Theta by definition.

∎

So we simply write Θ(log⁡n)\Theta(\log n). (In computer science, an unmarked log⁡\log often means log⁡2\log_2, because halving is everywhere; for asymptotics it doesn't matter.)

Theorem— Polynomials are beaten by exponentials

For every fixed kk, nk=o(2n)n^k = o(2^n). In particular 2n≠O(nk)2^n \ne O(n^k).

Proof

Take logarithms: log⁡2(nk/2n)=klog⁡2n−n\log_2 (n^k / 2^n) = k \log_2 n - n. Since log⁡2n/n→0\log_2 n / n \to 0 (see Exponential and logarithmic functions), we have klog⁡2n−n=n (klog⁡2n/n−1)→−∞k \log_2 n - n = n\,(k \log_2 n / n - 1) \to -\infty, so nk/2n→0n^k / 2^n \to 0. By the limit test, nk=O(2n)n^k = O(2^n) but not Ω(2n)\Omega(2^n), which also rules out 2n=O(nk)2^n = O(n^k).

∎

In practice you rarely go back to the definitions, because a few rules cover most cases:

  • Constant factors vanish: c⋅f=Θ(f)c \cdot f = \Theta(f) for any constant c>0c > 0.
  • Sums are dominated by their largest term: f+g=Θ(max⁡(f,g))f + g = \Theta(\max(f, g)). Doing a Θ(n)\Theta(n) step and then a Θ(n2)\Theta(n^2) step costs Θ(n2)\Theta(n^2).
  • Products multiply: a loop that runs Θ(f)\Theta(f) times with a body costing Θ(g)\Theta(g) costs Θ(f⋅g)\Theta(f \cdot g), provided the body's cost doesn't vary too much between iterations (if it does, add up the iterations exactly, as below).
  • Transitivity: if f=O(g)f = O(g) and g=O(h)g = O(h) then f=O(h)f = O(h); the same for Ω\Omega and Θ\Theta.
ExplanationH

The common growth rates

A handful of growth rates appear again and again. Here they are, slowest-growing first, with typical sources:

GrowthNameTypical source
11constantreading xs[i]; a dictionary lookup (on average)
log⁡n\log nlogarithmichalving the problem each step: binary search
nnlinearone pass over the data
nlog⁡nn \log nlinearithmicgood sorting algorithms; divide and conquer
n2n^2quadraticall pairs: the nested loop above
n3n^3cubicall triples; the textbook matrix multiplication
2n2^nexponentialtrying every subset
n!n!factorialtrying every ordering
05101520050100input size nsteps2ⁿn²n log nnlog n
Steps against input size for the common growth rates, for n up to 20. The exponential and quadratic curves leave the chart early; on this scale log n is almost flat.

Numbers make the differences vivid. Suppose a machine does 10810^8 simple steps per second, a fair order of magnitude for compiled code (Python is typically ten to a hundred times slower per step). Then, roughly:

GrowthSteps for n=103n = 10^3Steps for n=106n = 10^6Largest nn in about one second
log⁡2n\log_2 n1020astronomically large
nn10310^310610^610810^8
nlog⁡2nn \log_2 n10410^42×1072 \times 10^7about 4×1064 \times 10^6
n2n^210610^6101210^{12}10410^4
n3n^310910^9101810^{18}about 460
2n2^nabout 1030110^{301}(hopeless)about 26

Look at the last column from the other side. If you buy a computer 100 times faster, a linear algorithm handles inputs 100 times bigger, a quadratic one only 10 times bigger, and an exponential one only about 7 more items, since 27≈1002^7 \approx 100. Better hardware helps good algorithms most. The divide between polynomial growth (nkn^k) and exponential growth is the starting point of complexity theory, which asks which problems have polynomial-time algorithms at all; see Computational complexity in Lumenary Math and Hard problems later in this course.

Worked examplesH

Counting steps in code

Most running-time analysis comes down to a few loop patterns. In each, count how many times the innermost statement runs, as an exact sum where you can, then simplify.

One loop over the data. for x in xs: with a constant-cost body runs nn times: Θ(n)\Theta(n).

Two independent nested loops. for i in range(n): for j in range(n): runs the inner body n⋅nn \cdot n times: Θ(n2)\Theta(n^2).

A triangular loop. When the inner loop starts after the outer index, as in has_duplicate_pairs, the inner body runs (n−1)+(n−2)+⋯+1+0(n-1) + (n-2) + \dots + 1 + 0 times:

∑i=0n−1(n−1−i)=∑k=0n−1k=n(n−1)2=Θ(n2).\sum_{i=0}^{n-1} (n - 1 - i) = \sum_{k=0}^{n-1} k = \frac{n(n-1)}{2} = \Theta(n^2).

Half the work of the full square, but the same growth rate: constants don't change the class.

A halving loop. while n > 1: n = n // 2 runs ⌊log⁡2n⌋\lfloor \log_2 n \rfloor times, because after kk iterations nn has been divided by about 2k2^k, and the loop stops once 2k2^k exceeds nn. So Θ(log⁡n)\Theta(\log n). Doubling loops (j = 1; while j < n: j *= 2) are logarithmic for the same reason.

A loop inside a halving loop, or the reverse. for i in range(n): around a doubling while loop costs n⋅Θ(log⁡n)=Θ(nlog⁡n)n \cdot \Theta(\log n) = \Theta(n \log n).

The program below counts the steps of each pattern and compares them with the formulas.

python
import math

def steps_square(n):
    steps = 0
    for i in range(n):
        for j in range(n):
            steps += 1
    return steps

def steps_triangle(n):
    steps = 0
    for i in range(n):
        for j in range(i + 1, n):
            steps += 1
    return steps

def steps_halving(n):
    steps = 0
    while n > 1:
        n = n // 2
        steps += 1
    return steps

def steps_n_log_n(n):
    steps = 0
    for i in range(n):
        j = 1
        while j < n:
            j *= 2
            steps += 1
    return steps

print(f"{'n':>5} {'square':>8} {'triangle':>9} {'n(n-1)/2':>9} {'halving':>8} {'floor(log2 n)':>14} {'n log':>7}")
for n in [8, 100, 1000]:
    print(f"{n:>5} {steps_square(n):>8} {steps_triangle(n):>9} {n * (n - 1) // 2:>9}"
          f" {steps_halving(n):>8} {math.floor(math.log2(n)):>14} {steps_n_log_n(n):>7}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Hidden loops

A single line of Python can hide a loop, and the analysis must count it. Typical costs in CPython, the standard Python implementation:

OperationCost
xs[i], xs[i] = v, len(xs)Θ(1)\Theta(1)
xs.append(v), xs.pop()Θ(1)\Theta(1) amortised (see below)
xs.insert(0, v), xs.pop(0)Θ(n)\Theta(n): every item shifts along
v in xs, xs.index(v), xs.count(v)Θ(n)\Theta(n): a search through the list
xs[a:b], xs.copy()Θ(b−a)\Theta(b - a), Θ(n)\Theta(n): a copy is made
v in s, s.add(v) for a set; d[k] for a dictΘ(1)\Theta(1) on average
sorted(xs), xs.sort()Θ(nlog⁡n)\Theta(n \log n) worst case

So a loop that does if v in xs: on a list inside a for over nn items is quadratic, even though it looks like a single loop. That one hidden cost is the entire difference between the two duplicate checkers at the start of the lesson.

ExplanationH

Best, worst and average case

Consider linear search: look through a list from the front until you find a target tt.

  • Best case: tt is first. One comparison: Θ(1)\Theta(1).
  • Worst case: tt is last or absent. nn comparisons: Θ(n)\Theta(n).
  • Average case: if tt is present and equally likely to be at each of the nn positions, the expected number of comparisons is 1n(1+2+⋯+n)=n+12\frac{1}{n}(1 + 2 + \dots + n) = \frac{n+1}{2}, which is Θ(n)\Theta(n).

Notice that there are two independent choices here. The case (best, worst, average) chooses which function we are describing. The notation (OO, Ω\Omega, Θ\Theta) chooses what kind of bound we state about that function. "The worst-case running time of linear search is Θ(n)\Theta(n)" and "its best-case running time is Θ(1)\Theta(1)" are both precise, true statements. "Linear search is O(n)O(n)" is also true, since every case is at most linear, but it is a weaker statement.

Engineers usually quote the worst case, because it is a guarantee that no input, however unlucky or malicious, does worse. Average-case statements are only as good as their assumption about the inputs, which real data (already sorted, or crafted by an attacker) often breaks. The amortised cost, next, is a worst-case guarantee about sequences of operations.

Worked examplesH

Amortised cost: why append is cheap

A Python list stores references to its items in one contiguous block of memory, so that xs[i] can be found by arithmetic in one step. But then what happens when you append to a list whose block is full? A new, bigger block must be allocated and every existing reference copied across. That single append costs Θ(n)\Theta(n). If that happened on every append, building a list of nn items would cost Θ(n2)\Theta(n^2).

The trick, used by Python's lists, Java's ArrayList, C++'s std::vector and many others, is to over-allocate: when the block is full, grow its capacity by a constant factor, not by a constant amount. Then expensive appends become rarer and rarer as the list grows.

Definition— amortised cost

An operation has amortised cost aa if, starting from an empty structure, every sequence of mm such operations costs at most m⋅am \cdot a in total, in the worst case. Individual operations may be expensive, as long as they are rare enough to be paid for by the cheap ones.

Theorem— Doubling gives constant amortised appends

If a dynamic array starts with capacity 1 and doubles its capacity whenever an append finds it full, then any sequence of nn appends performs fewer than 2n2n copies in total, so each append costs O(1)O(1) amortised.

Proof

Copies happen only when the array is full, that is, when its size is a power of two: at sizes 1,2,4,…,2k1, 2, 4, \dots, 2^k where 2k<n2^k < n. The total number of items copied is

1+2+4+⋯+2k=2k+1−1<2⋅2k<2n.1 + 2 + 4 + \dots + 2^k = 2^{k+1} - 1 < 2 \cdot 2^k < 2n.

Adding the nn writes of the new items themselves, the whole sequence costs fewer than 3n3n steps, which is O(1)O(1) per append.

∎

The same argument works for any growth factor r>1r > 1: the copy sizes form a geometric series summing to at most about rr−1⋅n\frac{r}{r-1} \cdot n. CPython uses a gentle factor of about 1.1251.125 plus a small constant (see listobject.c in the references), trading more copies for less wasted memory. Growing by a fixed amount instead, say 100 slots at a time, breaks the guarantee: copy sizes 100,200,300,…100, 200, 300, \dots add up to Θ(n2)\Theta(n^2).

python
import sys

# Watch a real list's memory jump only now and then as it grows
xs = []
last = sys.getsizeof(xs)
changes = []
for i in range(1, 129):
    xs.append(i)
    size = sys.getsizeof(xs)
    if size != last:
        changes.append(i)
        last = size
print("The list's block grew when its length reached:", changes)

# Count copies for two growth strategies
def copies_needed(n, grow):
    capacity, size, copies = 1, 0, 0
    for _ in range(n):
        if size == capacity:
            copies += size              # move every item to the new block
            capacity = grow(capacity)
        size += 1
    return copies

def double(c):
    return 2 * c

def add_100(c):
    return c + 100

for n in [1000, 10_000, 100_000]:
    d = copies_needed(n, double)
    a = copies_needed(n, add_100)
    print(f"n = {n:>7}: doubling {d:>7} copies ({d / n:.2f} per append);"
          f" +100: {a:>10} copies ({a / n:.1f} per append)")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The exact sizes depend on the Python version and on whether it runs on a 64-bit machine or (as in the browser) a 32-bit WebAssembly build, but the gaps between growth points widen as the list gets longer. And the copy counts tell the story: with doubling, the cost per append stays below 2 however large nn gets; with fixed-size growth, it climbs with nn. You'll build a dynamic array yourself in Lists, stacks and queues.

ComputationC

Timing experiments

Analysis predicts; experiment checks. The most useful experiment is the doubling experiment: run the program on inputs of size nn, 2n2n, 4n4n, … and look at the ratio of successive times. If T(n)≈c nkT(n) \approx c\, n^k, then

T(2n)T(n)≈c (2n)kc nk=2k,\frac{T(2n)}{T(n)} \approx \frac{c\,(2n)^k}{c\, n^k} = 2^k,

so a ratio near 2 suggests linear growth, near 4 quadratic, near 8 cubic. The unknown constant cc, which depends on the machine, cancels out. Taking log⁡2\log_2 of the ratio estimates the exponent kk directly.

Some care makes timings trustworthy: use time.perf_counter() (a high-resolution clock), repeat each measurement and keep the minimum (other activity on the machine can only make a run slower, never faster), and use inputs large enough that each run takes at least a few milliseconds. Python's timeit module packages these habits.

python
import math
import time

def has_duplicate_pairs(ids):
    n = len(ids)
    for i in range(n):
        for j in range(i + 1, n):
            if ids[i] == ids[j]:
                return True
    return False

def has_duplicate_set(ids):
    seen = set()
    for x in ids:
        if x in seen:
            return True
        seen.add(x)
    return False

def best_time(f, data, repeats=3):
    best = float("inf")
    for _ in range(repeats):
        start = time.perf_counter()
        f(data)
        best = min(best, time.perf_counter() - start)
    return best

def doubling(f, sizes):
    previous = None
    for n in sizes:
        t = best_time(f, list(range(n)))     # distinct items: the worst case
        if previous is None:
            print(f"  n = {n:>7}: {t * 1000:8.2f} ms")
        else:
            ratio = t / previous
            print(f"  n = {n:>7}: {t * 1000:8.2f} ms   ratio {ratio:4.1f}   exponent about {math.log2(ratio):.1f}")
        previous = t

print("all pairs:")
doubling(has_duplicate_pairs, [400, 800, 1600])
print("with a set:")
doubling(has_duplicate_set, [50_000, 100_000, 200_000])
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Your times will differ from anyone else's, but the ratios should come out near 4 for the pairs version and near 2 for the set version, as the analysis predicts. If a measured ratio disagrees with your analysis, one of them is wrong, and finding out which is always instructive. (For tiny nn, fixed overheads dominate and ratios drift towards 1.)

Memory can be analysed the same way. has_duplicate_set uses Θ(n)\Theta(n) extra memory for its set, while has_duplicate_pairs uses Θ(1)\Theta(1). Spending memory to save time is one of the most common trades in computing.

Common misconceptionsH

Common misconceptions

Misconception

"O(n)O(n) means it takes nn steps." It means at most a constant times nn, for large enough nn. An algorithm taking 1000n+1061000n + 10^6 steps is O(n)O(n), and so is one taking log⁡n\log n steps: OO is only an upper bound.

Misconception

"Big-O means worst case; big-Ω means best case." The case and the notation are independent choices. You can give an OO bound on the best case or an Ω\Omega bound on the worst case. "Comparison sorting needs Ω(nlog⁡n)\Omega(n \log n) comparisons in the worst case" is a famous lower bound on a worst case, which you'll meet in Searching and sorting.

Misconception

"Constants never matter." They don't affect the growth class, but they matter enormously in practice. For small inputs a Θ(n2)\Theta(n^2) algorithm with a tiny constant can beat a Θ(nlog⁡n)\Theta(n \log n) one with a large constant, which is why Python's own sort switches to insertion sort for short stretches of data. Memory access patterns can also change real speed by large factors, as The memory hierarchy explains.

Misconception

"Computers are so fast now that efficiency doesn't matter." Unless the algorithm is linear or better, a faster machine multiplies the solvable problem size by much less than its speed-up, and data keeps growing too.

History & global context

Where the notation came from

The symbol OO was introduced by the number theorist Paul Bachmann in 1894 and popularised by Edmund Landau, which is why these are still called Landau symbols; they described the error in approximations, such as counting primes. In 1965 Juris Hartmanis and Richard Stearns measured problems by the time a machine needs as a function of input length, founding complexity theory (Turing Award, 1993), and in the same year Alan Cobham and Jack Edmonds independently proposed "polynomial time" as the mathematical stand-in for "efficient". In 1976 Donald Knuth, whose The Art of Computer Programming helped make the analysis of algorithms a discipline, wrote a short letter fixing the meanings of Ω\Omega and Θ\Theta used here; before that, authors used Ω\Omega in different senses.

Exercises

Exercises

1. Measuring the cost of a program

CoreHuman

Which of these statements are true? Choose all that apply.

Choose all that apply

2. Measuring the cost of a program

Warm-upHuman

To prove 3n+10=O(n)3n + 10 = O(n), you choose the constant c=4c = 4. What is the smallest n0n_0 such that 3n+10≤4n3n + 10 \le 4n for every n≥n0n \ge n_0?

3. Measuring the cost of a program

CoreComputational

What is the running time of this code, as a function of nn?

total = 0
for i in range(n):
    j = n
    while j > 1:
        j = j // 2
        total += 1
for k in range(n):
    total += k
Choose one

4. Measuring the cost of a program

CoreHuman

An algorithm with running time Θ(n2)\Theta(n^2) processes n=10 000n = 10\,000 items in one hour. You move it to a computer that is 100 times faster. Roughly how many items can it process in one hour now?

Choose one

5. Measuring the cost of a program

CoreHuman

Linear search checks the items of a list from the front until it finds the target. Which statement is correct and most informative?

Choose one

6. Measuring the cost of a program

CoreComputational

The starter is the all-pairs duplicate checker from the lesson. It is correct, but it makes Θ(n2)\Theta(n^2) comparisons. Rewrite has_duplicate(items) so that it does Θ(n)\Theta(n) work on average, using a set.

The checker counts how many times items are compared with ==: on a list of 1000 distinct items, your function may make at most 2000 comparisons.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Measuring the cost of a program

CoreComputational

Write estimate_exponent(n1, t1, n2, t2), which takes two measurements (input size n1 took t1 seconds, size n2 took t2 seconds) and returns the exponent kk for which t≈c nkt \approx c\, n^k fits both. For example, if doubling nn multiplies the time by 4, the answer is 2.

Hint: from t2/t1=(n2/n1)kt_2 / t_1 = (n_2 / n_1)^k, solve for kk with logarithms. import math gives you math.log.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

8. Measuring the cost of a program

StretchComputational

Simulate a dynamic array. Write total_copies(n, factor) that returns how many item copies are made while appending n items to an array that:

  • starts with capacity = 1 and size = 0;
  • on each append, if size == capacity, first copies all size items to a new block and sets capacity = max(capacity + 1, int(capacity * factor));
  • then stores the new item (size += 1; this write is not a copy).

For factor = 2 the answer for n = 5 is 1 + 2 + 4 = 7. Then check the theorem: the tests confirm that for factor = 2 the copies are always fewer than 2 * n.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Further reading and resources