Sequences, sums, asymptotics, and recurrences

Two nested loops are both described as “quadratic,” but one executes n squared body steps and the other n(n−1)/2. A measured runtime includes interpreter overhead, allocation, data representation, and the chosen input. An asymptotic bound describes how a particular cost model grows as the size increases. These quantities are connected, but they are not interchangeable.

This module builds exact counts first, then proves their growth and solves recursive cost models. You will state which operation is charged, what input size means, and whether the count is worst case, best case, or aggregate across a sequence. A compact Big O label should be the conclusion of an argument rather than its starting assumption.

Retrieval check: expand a finite double sum, use a logarithm to invert a power, and write a complete induction proof. Review Module 01 and Module 04 if needed. The core requires those modules; an optional binomial growth argument also uses Module 05. Counts here assume finite inputs and operations that terminate.

A sequence assigns a value to each permitted integer index. An arithmetic sequence has a constant difference d: $a_i=a_0+id$. Summing n terms indexed zero through n−1 gives $na_0+d\sum_{i=0}^{n-1}i=na_0+d\,n(n-1)/2$. The formula is valid at n=0 because both parts vanish. State the starting index before substituting a familiar sum formula; moving from zero-based to one-based terms can change the constant.

The sum of integers from one through n is n(n+1)/2. Reverse the finite sum and add termwise: each paired term is n+1 and there are n pairs, so twice the sum is n(n+1). Module 04 also proved the formula by induction. The two arguments cover the same declared domain in different ways. Neither depends on extrapolating a plot of successful calculations.

A geometric sequence multiplies by a fixed ratio r: terms $a,ar,ar^2,\ldots$. For n≥0 and r≠1,

To derive it, call the sum S, multiply by r, and subtract. All intermediate powers cancel, leaving $(1-r)S=a(1-r^n)$. Division requires r≠1. When r=1 the sum is na. The n=0 formula gives zero, matching the empty sum. A ratio zero also fits the finite formula; avoid replacing the first term with an ambiguous unexamined expression.

Doubling work across levels gives $1+2+\cdots+2^{h-1}=2^h-1$. Constant work across h levels gives h times that cost. Work halving across levels gives a sum bounded by twice its first term. These three patterns will explain recurrence-tree cases later. They are finite sums; no result about infinite series is being assumed here.

A telescoping sum writes terms as consecutive differences, so interior parts cancel. If the terms are $b_{i+1}-b_i$, then $\sum_{i=0}^{n-1}(b_{i+1}-b_i)=b_n-b_0$. Expand three terms to see each cancellation and verify the boundary. The remaining endpoints depend on the exact first and last indices, so changing bounds requires changing the endpoint expression too.

Sum linearity allows coefficients and separate terms to be combined, but only when the corresponding index domains match. $\sum_i(a_i+b_i)=\sum_i a_i+\sum_i b_i$ uses the same finite index set. If one term is defined only for a smaller range, specify the missing values or split the range. A computational cost model can also add disjoint operation categories, provided the accounting does not charge the same event twice by mistake.

Growth analysis compares nonnegative functions as the input size increases. Familiar candidates include constants, logarithms, n, n log n, polynomials, and exponentials. A table gives useful intuition about scale but does not prove an eventual comparison for every large input. The formal definitions in the next section state that eventual obligation and specify its constants.

| n | $\log_2n$ | n | $n\log_2n$ | $n^2$ | $2^n$ | |---|---|---|---|---|---|---| | 2 | 1 | 2 | 2 | 4 | 4 | | 4 | 2 | 4 | 8 | 16 | 16 | | 8 | 3 | 8 | 24 | 64 | 256 | | 16 | 4 | 16 | 64 | 256 | 65536 |

Logarithms with different fixed bases greater than one differ by a positive constant: $\log_b n=\ln n/\ln b$. Thus they have the same asymptotic growth class. The base still matters for an exact count. A binary doubling loop and a ternary multiplying loop have different integer iteration counts, even though both have logarithmic growth. Do not remove a base from an exact expression just because it can be ignored in a Theta classification.

Polynomial degree matters asymptotically while constants can dominate small inputs. A count 1000n may exceed n squared at n=10, but beyond n=1000 the quadratic count is larger. The crossover depends on constants and input range. A statement about eventual growth does not promise which implementation is faster for every practical dataset. It describes a model after a sufficiently large threshold.

Exponential growth eventually exceeds every fixed-degree polynomial. An optional proof using Module 05’s binomial theorem makes this precise for integer degree k≥0. For n≥2(k+1), $2^n\ge\binom n{k+1}\ge(n/2)^{k+1}/(k+1)!$. Every factor in the binomial numerator is at least n/2. Dividing by $n^k$ gives a lower bound proportional to n, so the exponential-to-polynomial ratio can exceed any fixed constant. The proof uses a fixed k; letting k depend on n would change the claim.

Input size must be defined. A graph algorithm may depend on both vertex count and edge count, and a matrix multiplication on three dimensions. A training procedure may additionally depend on batch size and iteration count. Collapsing all parameters to one symbol without describing their relationship can hide the relevant cost. Later modules will retain shape parameters when counting linear-algebra operations.

Bit length is another size choice. An integer of numeric value N requires roughly log₂N binary digits. An algorithm taking N elementary iterations is exponential in that bit length when N is a power of two. Treating the value and its representation length as the same input size can reverse an efficiency interpretation. For the loop labs n is an explicit count parameter; the charged body steps are not a complete bit-complexity analysis.

Growth also depends on the quantity being bounded. Memory allocation, comparisons, arithmetic operations, and communication may each have different counts. A loop with constant body-entry count can perform large-integer multiplication whose bit cost grows with its operands. The simple unit-cost model is useful when its assumptions match the intended level of analysis, and its limits should be stated rather than hidden.

For eventually nonnegative functions f,g with g positive for all sufficiently large natural n, $f\in O(g)$ means there exist constants c>0 and n₀ such that every n≥n₀ satisfies $f(n)\le c g(n)$. The constants are fixed before considering every sufficiently large n. You may not choose a different c for each input and call that the same Big O proof. We sometimes write f=O(g) as conventional shorthand for membership in this class.

$f\in\Omega(g)$ means some fixed c>0 and n₀ give $f(n)\ge c g(n)$ for all n≥n₀. $f\in\Theta(g)$ means both upper and lower bounds hold, equivalently there are $c_1,c_2>0$ and n₀ with $c_1g(n)\le f(n)\le c_2g(n)$ for every n≥n₀. Big O is an upper bound; Theta is a tight growth-class statement in this two-sided sense.

The same f is also O(n cubed), because n²≤n³ for n≥1. That upper bound is correct but weaker. Calling Big O an exact rate would incorrectly treat both descriptions as equalities. Conversely, f=n is O(n²) but not Theta(n²): no positive lower constant times n² can stay below n forever. An upper bound alone does not supply tightness.

Little o is stronger than Big O. $f\in o(g)$ means for every ε>0 there is a threshold n₀ such that all n≥n₀ satisfy $f(n)<\varepsilon g(n)$. No single positive multiplicative scale remains necessary: relative to g, f eventually becomes smaller than any chosen fraction. The threshold may depend on ε, while it remains fixed across all later n for that chosen ε.

For n compared with n², choose an integer n₀>1/ε. Then for n≥n₀, $n/n^2=1/n<\varepsilon$, proving n=o(n²). In contrast n² is O(n²) but not o(n²): choose ε=1/2 and the required inequality is impossible. These direct inequality arguments do not assume the calculus limit notation that will arrive in Module 15.

Quantifier order connects the definitions to Module 02. Big O uses “there exist c,n₀, for every later n”; little o uses “for every ε, there exists n₀, for every later n.” Changing the order changes the requirement. A finite graph of f/g may suggest good constants, but a proof must cover the unbounded tail with an inequality or another justified theorem.

Specify which f is being analysed. Worst-case time at size n is the maximum over allowed size-n inputs; best case is the minimum. An average-case count needs a probability distribution over inputs. Each of those functions can separately be O, Omega, or Theta of a comparison function. Big O itself does not mean worst case, and Omega itself does not mean best case. Those labels describe the chosen cost function, while asymptotic symbols describe bounds on it.

Equivalent constants and lower-order terms can be suppressed after proof, but not before the model is clear. If an implementation changes from fixed-width scalars to arbitrary-precision integers or from prebuilt data to on-demand construction, the charged primitive costs may change. Revisit the model rather than carrying an old asymptotic label across a different operation definition.

Choose a charged operation before counting. The first lab charges one operation for each entry into a selected loop body. It does not separately charge every guard comparison, increment, list access, or Python instruction. This restricted count is useful for understanding loop shapes. A fuller model could add those categories; its exact constants would change, and its growth might also change if the body contains a nonconstant operation.

A rectangular nested loop with n outer iterations and n inner iterations has n² body entries by multiplication. A triangular loop with i inner iterations at outer index i has n(n−1)/2, as derived earlier. Both are Theta(n²) for sufficiently large n, though their exact counts differ and the triangular loop has zero entries at n=1. An asymptotic threshold can exclude those small cases without denying their exact behaviour.

The doubling loop’s guard is evaluated once more after the last body entry. If comparisons are the charged operation instead, the exact count is h+2 for n≥1 and one at n=0. Both counts have logarithmic growth on positive sizes. State which one your formula describes; an exact-count mismatch can be a model mismatch rather than a wrong asymptotic argument.

Input-dependent branches require an explicit cost function. First-match search over a nonempty list can use one comparison when the first element matches. If the target is absent or first appears last, it uses n comparisons. The worst-case comparison count is n, the best-case count one for n≥1. An average count cannot be inferred merely from these extremes; it requires a distribution over target presence and position.

A universal worst-case bound describes every allowed input, but its tightness requires at least one family reaching the scale. The search upper bound holds because no position is inspected twice. Absent-target lists witness n comparisons at every size. For a best-case bound, identify inputs attaining the minimum without changing the input domain. A search that assumes success at the first position has a different contract, rather than an improved worst case for general search.

Multiparameter counts remain useful. A loop scanning m rows with n entries per row has mn charged entries, not necessarily n². If m is fixed independently of n, growth in n is linear; if m=n it is quadratic in that shared size. Matrix-based AI workloads frequently need several shape parameters plus iteration count. The analysis should retain them until the intended scaling relationship is declared.

Measured elapsed time is an observation of real execution under a machine, interpreter, input, and measurement scope. Timing array construction inside a supposedly constant-query measurement charges setup that a prebuilt-query model excluded. Cache behaviour, scheduling noise, compiler behaviour, and integer sizes can also change observations. Repeating measurements helps describe variability but does not by itself prove an unbounded asymptotic claim.

Use measurements to investigate a model, not to rename it silently. Report what is included, what input family was used, and which operations were predicted. If the observation disagrees, inspect setup, hidden work, and the cost of primitives before deciding whether the derivation is wrong. Later numerical-computation material extends this discipline to reproducibility and accuracy, as well as speed.

A timestamp returned in nanoseconds does not guarantee that the clock resolves every individual nanosecond. A very short query can receive identical start and end readings and appear to take zero measured time. That is a measurement limitation, not proof of zero work. Batching many queries can make the interval measurable, but the batch also includes its loop and call overhead; report that scope rather than interpreting the quotient as a perfect isolated primitive cost.

The lab keeps short timings visible precisely to make those limits discussable. It reports the best of seven runs, which is a selected observation rather than an average or a distributional guarantee. A stronger empirical investigation would record the environment, use a range of geometrically increasing sizes, separate setup, preserve repeated observations, and compare them with a justified cost prediction. None of those improvements changes the logical difference between observing a finite experiment and proving an eventual bound.

A recurrence defines a cost using smaller input costs and work done at the current level. It needs a base condition, an allowed size domain, and a justification from the algorithm. For equal halves, we first restrict sizes to n=2ʰ with h≥0, so halving reaches one exactly. Floors and ceilings for other sizes require a separate argument rather than silently evaluating a fractional problem size.

Consider $T(n)=2T(n/2)+n$ for n>1 and T(1)=1. The two children model two size-n/2 subproblems, and n models nonrecursive work. After one expansion, $T(n)=4T(n/4)+2n$. After j levels, there are $2^j$ children of size $n/2^j$, and their total level work is n. The depth to leaves is h=log₂n.

The same method solves $T(n)=T(n/2)+n$, T(1)=1. Level work halves, so the nonleaf work is $n+n/2+\cdots+2=2n-2$, with one final leaf: T(n)=2n−1. For four half-size children, $T(n)=4T(n/2)+n$, the level work doubles, giving n(2ʰ−1)=n(n−1) before leaves and n² leaf work. Total T(n)=2n²−n.

These recurrences count a mathematical work model. A program computing the recurrence values with memoisation may evaluate the numerical formula quickly without executing every modelled child operation. The lab’s cache avoids repeating identical numerical subproblems; its runtime is not the runtime represented by T. Confusing a model evaluator with the modelled algorithm would invalidate the interpretation of a measured time.

Expansion also handles decreasing-by-one sizes. If $T(n)=T(n-1)+n$, T(0)=0, repeated substitution gives $T(n)=\sum_{i=1}^n i=n(n+1)/2$. The depth is n rather than logarithmic. Treating n−1 as though it were n divided by a fixed constant gives the wrong tree and is outside the equal-ratio theorem below. First draw what the recurrence actually says.

To verify a proposed bound by substitution, assume the bound for smaller sizes and show the recurrence implies it for the current size, with valid base coverage. For the balanced two-child recurrence, guessing T(n)≤Cn gives $2C(n/2)+n=(C+1)n$, which does not close the proposed upper bound: the accumulated level work needs the logarithmic factor. For the one-child recurrence, T(n)≤2n does close, while the exact 2n−1 additionally retains the base’s correction. Track the smaller-size factors and the nonrecursive work explicitly.

A recurrence also assumes the subproblem count and size are accurate. If the code makes unequal-size calls, performs extra data copying, or stops on an input-dependent condition, revisit the model. A recursion tree based on average balance is not a worst-case proof for an algorithm that can split extremely unevenly. Classifying the exact recurrence comes after deriving it from the intended input family and charged operations.

For a clear proved special case of the Master theorem, suppose $T(n)=aT(n/b)+cn^d$, with a fixed positive T(1), integer a≥1, fixed integer b>1, c>0, d≥0, and sizes n=bʰ. Let p=log_b a. At level j, work is $cn^d(a/b^d)^j$; leaves contribute Theta(nᵖ). Thus a finite geometric sum explains the three cases:

If q=a/bᵈ>1, the level sum has the scale of its final levels, and $n^dq^h=n^p$. If q=1, h equal-cost levels produce the logarithmic factor. If q<1, the level sum is bounded above by a constant times its root cost and below by the root itself. The leaf term does not upset those cases. These are conclusions of the tree sum under the stated conditions.

More general formulations replace the pure power with f(n). A common basic version compares f with nᵖ using a polynomial gap: f=O(nᵖ⁻ε), f=Theta(nᵖ), or f=Omega(nᵖ⁺ε) for some ε>0. In the third case it also requires regularity $a f(n/b)\le c_0 f(n)$ for some c₀<1 eventually. State the version and conditions you are applying. The balanced case is not “anything slightly below or above nᵖ,” and the pure-power proof does not automatically cover arbitrary oscillating f.

The borderline recurrence $T(n)=2T(n/2)+n/\log_2n$, T(1)=1, on n=2ʰ uses the extra work only for n≥2. Its nonleaf level work is n/(h−j), so exact expansion gives $T(n)=n(1+H_h)$, where $H_h=1+1/2+\cdots+1/h$. The basic f=Theta(n) balanced case does not apply, and f is not polynomially smaller than n. Derive or use a theorem covering the case instead of forcing it into an inapplicable rule. The exact expression is sufficient for the lab; its further asymptotic simplification is optional.

Amortised analysis bounds the total cost of an operation sequence and divides by the number of operations. It needs no probability distribution. A costly operation can coexist with constant amortised cost if other operations are cheap often enough. Worst-case single-operation cost, average-case cost under a distribution, and amortised sequence cost are different statements.

An amortised claim must cover every allowed sequence in its model. Here append-only sequences make occupancy increase and trigger capacities geometrically. Adding a shrink-on-every-delete rule could produce repeated resize work unless its thresholds are designed carefully; the append-only proof would not automatically cover arbitrary alternating operations. Identify the operation family before reusing the result.

Use Python 3.11 or later; no packages are required. See the Python primer. The recurrence lab uses @cache to reuse numerical results of identical function arguments; it computes a cost value rather than performing the modelled recursion’s entire work. The timing lab’s numbers vary across builds and machines. Both editions display the same actual captured run. Each lab explanation earns ten points: prediction 3, model interpretation 4, fault diagnosis 3.

Fifty minutes: predict every output for zero, one, four, eight, and sixteen. Run and distinguish rectangular, triangular, and doubling body counts. The reference bit_length() agrees with floor(log₂n)+1 for positive integers; at zero the body count is zero. Change the triangular inner stop from i to i+1 and update the exact formula. Then explain how charging guards would change the exact counts without automatically changing their eventual growth.

Download lab1_loop_counts.py

"""Charge one operation per body entry, not elapsed time or every instruction."""


def counts(n):
    rectangular = triangular = doubling = 0
    for _ in range(n):
        for _ in range(n):
            rectangular += 1
    for i in range(n):
        for _ in range(i):
            triangular += 1
    i = 1
    while i <= n:
        doubling += 1
        i *= 2
    assert rectangular == n * n
    assert triangular == n * (n - 1) // 2
    assert doubling == n.bit_length()
    return rectangular, triangular, doubling


def main():
    print("n | rectangular body | triangular body | doubling body")
    for n in (0, 1, 4, 8, 16):
        print(n, "|", " | ".join(map(str, counts(n))))
    print("Body-entry counts exclude loop guards and integer-operation bit costs.")


if __name__ == "__main__":
    main()

n | rectangular body | triangular body | doubling body
0 | 0 | 0 | 0
1 | 1 | 0 | 1
4 | 16 | 6 | 3
8 | 64 | 28 | 4
16 | 256 | 120 | 5
Body-entry counts exclude loop guards and integer-operation bit costs.

Fifty minutes: predict the n=8 row and derive each full solution with base T(1)=1. Run and compare one, two, and four half-size children. Change the base to two and calculate the new leaf contribution before execution. Preserve powers-of-two input sizes; the script does not implement floor/ceiling analysis for arbitrary n. Explain why memoising the numerical model cannot be interpreted as speeding up every real algorithm represented by that recurrence.

Download lab2_recurrences.py

"""Exact recurrences for powers of two; the multiplier counts identical children."""
from functools import cache


@cache
def cost(n, branches):
    if n == 1:
        return 1
    return branches * cost(n // 2, branches) + n


def main():
    print("n | T1(n) | T2(n) | T4(n)")
    for exponent in range(7):
        n = 2 ** exponent
        values = [cost(n, branches) for branches in (1, 2, 4)]
        assert values == [2 * n - 1, n * (exponent + 1), 2 * n * n - n]
        print(n, "|", " | ".join(map(str, values)))
    print("All bases T(1)=1, all non-leaf work=n, all child sizes=n/2.")
    print("Caching computes the numerical model; it is not the runtime of a real recursive algorithm.")


if __name__ == "__main__":
    main()

n | T1(n) | T2(n) | T4(n)
1 | 1 | 1 | 1
2 | 3 | 4 | 6
4 | 7 | 12 | 28
8 | 15 | 32 | 120
16 | 31 | 80 | 496
32 | 63 | 192 | 2016
64 | 127 | 448 | 8128
All bases T(1)=1, all non-leaf work=n, all child sizes=n/2.
Caching computes the numerical model; it is not the runtime of a real recursive algorithm.

Fifty minutes: identify which timing includes list construction, and predict the exact recurrence ratios independently of the measured nanoseconds. A zero or tiny query interval may reflect clock resolution. The borderline work n/log₂n lies outside the basic balanced case; compare the exact harmonic expression instead. Finally predict append copies at m=8 and m=9 and explain why one costly resize is consistent with total charged cost below 3m. Allocation and zero-initialisation are outside that copy/write counter.

Download lab3_cost_traps.py

"""Measured scope, a borderline recurrence, and aggregate doubling-array costs."""
from fractions import Fraction
from time import perf_counter_ns


def measure(call):
    best = None
    for _ in range(7):
        start = perf_counter_ns()
        call()
        elapsed = perf_counter_ns() - start
        best = elapsed if best is None else min(best, elapsed)
    return best


def append_cost(m):
    storage, size, copies, writes = [None], 0, 0, 0
    for value in range(m):
        if size == len(storage):
            larger = [None] * (2 * len(storage))
            for i in range(size):
                larger[i] = storage[i]
                copies += 1
            storage = larger
        storage[size] = value
        writes += 1
        size += 1
    assert storage[:size] == list(range(m))
    assert m == 0 or copies + writes < 3 * m
    return copies, writes


def main():
    print("Timing scope: the query reads the first entry; setup creates n entries.")
    for n in (1000, 4000):
        items = list(range(n))
        query_only = measure(lambda: items[0] == 0)
        with_setup = measure(lambda: list(range(n))[0] == 0)
        print(f"n={n}: one comparison; query-only best={query_only} ns; including setup best={with_setup} ns")
    print("Times vary by run/machine; no asymptotic claim follows from these four measurements.")
    print("Borderline: T(2^h)=2*T(2^(h-1))+2^h/h, T(1)=1")
    total, harmonic = Fraction(1), Fraction(0)
    for h in range(1, 6):
        n = 2 ** h
        total = 2 * total + Fraction(n, h)
        harmonic += Fraction(1, h)
        assert total == n * (1 + harmonic)
        print(f"h={h}, n={n}: T/n={total/n}; exact=1+H_h")
    print("The basic balanced f(n)=Theta(n) case does not apply to n/log2(n).")
    for m in (0, 1, 2, 3, 4, 5, 8, 9, 16, 17):
        copies, writes = append_cost(m)
        print(f"appends={m}: copies={copies}, writes={writes}, charged total={copies+writes}")
    print("Charge model counts copies+writes, excluding allocation/initialisation costs.")


if __name__ == "__main__":
    main()

Timing scope: the query reads the first entry; setup creates n entries.
n=1000: one comparison; query-only best=100 ns; including setup best=3700 ns
n=4000: one comparison; query-only best=0 ns; including setup best=15400 ns
Times vary by run/machine; no asymptotic claim follows from these four measurements.
Borderline: T(2^h)=2*T(2^(h-1))+2^h/h, T(1)=1
h=1, n=2: T/n=2; exact=1+H_h
h=2, n=4: T/n=5/2; exact=1+H_h
h=3, n=8: T/n=17/6; exact=1+H_h
h=4, n=16: T/n=37/12; exact=1+H_h
h=5, n=32: T/n=197/60; exact=1+H_h
The basic balanced f(n)=Theta(n) case does not apply to n/log2(n).
appends=0: copies=0, writes=0, charged total=0
appends=1: copies=0, writes=1, charged total=1
appends=2: copies=1, writes=2, charged total=3
appends=3: copies=3, writes=3, charged total=6
appends=4: copies=3, writes=4, charged total=7
appends=5: copies=7, writes=5, charged total=12
appends=8: copies=7, writes=8, charged total=15
appends=9: copies=15, writes=9, charged total=24
appends=16: copies=15, writes=16, charged total=31
appends=17: copies=31, writes=17, charged total=48
Charge model counts copies+writes, excluding allocation/initialisation costs.

Exercises 1–12 take 140 planned minutes and earn five points each; two optional exercises add 25 minutes. State the size domain, charged operation, and bound witnesses. Give bases and a verification argument for every recurrence solution.

Nine automatic choices plus a reviewed written explanation make ten points. A bound answer needs the cost function and the constants’ scope, not only a familiar growth label.

Required, 25 minutes: use the sums and asymptotic-analysis material in the textbook linked by MIT Mathematics for Computer Science. Rewrite one bound with explicit quantifiers and provide its constants.

Required, 11 minutes: read the recurrence-tree and Master-theorem discussion in MIT 6.006 Recitation 3. Compare its polynomial-work cases with our proved power-of-b model and note the base assumptions.

Required, 9 minutes: use the textbook’s amortised-analysis selection to identify the total-cost argument and charged events. Contrast it with a worst-case single operation. These selections total forty-five minutes.

Optional: inspect the fuller conditions in MIT Master Theorem practice, and use Python’s performance-clock documentation to interpret units and resolution. The lesson’s examples and derivations are original.

Finite sums turn exact iteration patterns into formulas. Asymptotic definitions compare those formulas with fixed witnesses beyond a threshold. Recurrences encode smaller calls and nonrecursive work; tree expansion explains the cost at each level and the leaves. Theorems summarise patterns under conditions, while aggregate analysis bounds an operation sequence rather than each individual step.

Exit task: derive triangular and doubling body counts, prove a Theta statement with constants, solve and verify the balanced recurrence, and explain an expensive append within a linear prefix bound. Use exercises 60, lab explanations 30, and quiz 10. Keep size, primitive operations, input model, and measured scope explicit in every answer.

Module 07 analyses graphs using both structure and cost. Before it, explain why a scan of every vertex and every stored adjacency entry has a count depending on both quantities. A graph’s edge count is another parameter, not automatically its vertex count squared.