Algorithm Analysis and Correctness

Why count operations instead of seconds?

"My program took 0.8 s" tells you about one machine, one compiler, one input, and one moment. The same code can run five times faster on a newer laptop, slower while the JIT compiler is still warming up, or erratically when the garbage collector kicks in. What we want is a statement about the algorithm that stays true on every machine:

How does the number of basic steps grow as the input size n grows?

We therefore work in the RAM model (random-access machine): each simple operation — an arithmetic operation, a comparison, an assignment, an array access, a method call and return — costs one unit of time, and any memory cell can be read in constant time. We count those units as a function T(n) of the input size and then keep only how fast it grows.

Worked example: counting line by line. How many steps does this method take for an array of n elements?

static int sum(int[] a) {                     // n = a.length
    int total = 0;                            // runs 1 time
    for (int i = 0; i < a.length; i++)        // i = 0: 1 time; test: n + 1 times; i++: n times
        total += a[i];                        // runs n times
    return total;                             // runs 1 time
}

The loop test runs n + 1 times, not n: it is true n times and false once, at the end. Count one unit per line execution:

Line	Times executed
total = 0	1
i = 0	1
i < a.length	n + 1
total += a[i]	n
i++	n
return total	1
Total T(n)	3n + 4

Check with numbers: n = 1 gives 7 steps, n = 5 gives 19, n = 10 gives 34. Each extra element adds 3 steps. If you counted total += a[i] as 3 units (read, add, write) you would get 5n + 4 instead — a different constant, the same growth. That is why we soon throw the constants away: the part that matters is "grows like n".

Asymptotic notation: O, Ω, Θ

Numbers first. Take f(n) = 3n² + 5n + 2 and compare it with 3n² and 10n²:

n	3n²	f(n) = 3n² + 5n + 2	10n²
1	3	10	10
2	12	24	40
3	27	44	90
4	48	70	160
5	75	102	250

In every row, f(n) sits between 3n² and 10n². It is "sandwiched" by two multiples of n²:

   floor (Ω)                              ceiling (O)
     3n²      ≤      3n² + 5n + 2      ≤     10n²        for every n ≥ 1
   c = 3                                     c = 10         n₀ = 1

   n = 5:  75 ≤ 102 ≤ 250        n = 1000:  3 000 000 ≤ 3 005 002 ≤ 10 000 000

Notice that for large n the "+ 5n + 2" part hardly matters: f(1000) is only 0.17 % more than 3n². That picture is exactly the formal definition. Now the formal version:

Let f and g be functions from input sizes to non-negative numbers.

Notation	Definition	Read as
f(n) = O(g(n))	there exist constants c > 0 and n₀ ≥ 1 such that f(n) ≤ c · g(n) for all n ≥ n₀	f grows at most like g (upper bound)
f(n) = Ω(g(n))	there exist constants c > 0 and n₀ ≥ 1 such that f(n) ≥ c · g(n) for all n ≥ n₀	f grows at least like g (lower bound)
f(n) = Θ(g(n))	f(n) = O(g(n)) and f(n) = Ω(g(n))	f grows exactly like g (tight bound)

The constant c absorbs machine speed and constant factors; n₀ says "we only care about large inputs".

Why n₀? Compare n² with 100n. For n = 10: 100 against 1000, so n² is smaller. For n = 100 they are equal (10 000). For n = 200: 40 000 against 20 000, and from then on n² is always bigger. Small inputs can mislead; n₀ lets us ignore them.

Worked proof. Show that f(n) = 3n² + 5n + 2 is Θ(n²).

• Upper bound. For n ≥ 1 we have 5n ≤ 5n² and 2 ≤ 2n², so f(n) ≤ 3n² + 5n² + 2n² = 10n². Take c = 10, n₀ = 1: f(n) = O(n²).
• Lower bound. For n ≥ 1, 5n + 2 > 0, so f(n) ≥ 3n². Take c = 3, n₀ = 1: f(n) = Ω(n²).
• Both hold, so f(n) = Θ(n²).

The trick in the upper bound: replace every smaller term by the biggest power (5n ≤ 5n², 2 ≤ 2n² when n ≥ 1) and add the coefficients.

Disproving a bound. Is n² = O(n)? Suppose constants c and n₀ existed with n² ≤ c · n for all n ≥ n₀. Dividing by n gives n ≤ c for all n ≥ n₀ — false for any n larger than both c and n₀. So no such constants exist and n² ≠ O(n). In numbers: even with a generous c = 1000, the inequality n² ≤ 1000n fails at n = 1001.

The growth-rate hierarchy

Growth	Name	n = 10	n = 100	n = 1000	Typical example
1	constant	1	1	1	array access, HashMap.get (expected)
log n	logarithmic	3.3	6.6	10	binary search
n	linear	10	100	1000	linear search, one pass
n log n	linearithmic	33	664	9 966	merge sort
n²	quadratic	100	10⁴	10⁶	all pairs, selection sort
n³	cubic	1000	10⁶	10⁹	all triples, naive matrix multiplication
2ⁿ	exponential	1024	1.3 × 10³⁰	1.1 × 10³⁰¹	all subsets
n!	factorial	3.6 × 10⁶	9.3 × 10¹⁵⁷	≈ 4 × 10²⁵⁶⁷	all permutations

What happens when n doubles? This is the easiest way to feel the difference:

Growth	n = 1000 → n = 2000	Effect of doubling n
1	same	no change
log n	9.97 → 10.97	+1 step
n	1000 → 2000	×2
n log n	≈ 9 966 → ≈ 21 932	a bit more than ×2
n²	10⁶ → 4 × 10⁶	×4
n³	10⁹ → 8 × 10⁹	×8
2ⁿ	2¹⁰⁰⁰ → 2²⁰⁰⁰	the cost is squared

At a billion simple steps per second, an n² algorithm handles n = 10⁶ in about 17 minutes; an n log n algorithm needs 0.02 s. No hardware upgrade closes that gap.

Analysing code

Sequential blocks add; the largest term wins.

for (int i = 0; i < n; i++) total += a[i];          // n
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) count++;             // n²

n + n² = Θ(n²). For n = 1000 that is 1 000 + 1 000 000: the first loop is only 0.1 % of the work.

Nested loops multiply — when the bounds are independent. An inner loop that runs a constant number of times (say j < 100) contributes only a constant factor: the whole thing is Θ(n).

Dependent loops: count with a sum.

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        count++;

Trace with n = 8: when i = 0 the inner loop runs 7 times, when i = 1 it runs 6 times, and so on:

i	0	1	2	3	4	5	6	7
inner runs	7	6	5	4	3	2	1	0

Total 7 + 6 + … + 0 = 28 = 8 · 7 / 2. In general the inner loop runs n − 1, n − 2, …, 1, 0 times: (n − 1) + (n − 2) + … + 0 = n(n − 1)/2 = Θ(n²). Halving the work does not change the class. (A trick to remember the sum: pair the first and last terms, 7 + 0, 6 + 1, 5 + 2, 4 + 3 — four pairs of 7.)

Halving or doubling: logarithms.

int steps = 0;
while (n > 1) {
    n = n / 2;
    steps++;
}

Trace with n = 16: 16 → 8 → 4 → 2 → 1, so 4 steps, and 2⁴ = 16. With n = 100: 100 → 50 → 25 → 12 → 6 → 3 → 1, 6 steps (log₂ 100 ≈ 6.6, integer division rounds down).

After k iterations n has become about n / 2ᵏ; the loop stops when that reaches 1, i.e. after about log₂ n iterations — Θ(log n). The same holds for for (int i = 1; i < n; i *= 2).

Combine carefully. Two different-looking loops:

for (int i = 1; i < n; i *= 2)          // log n rounds
    for (int j = 0; j < n; j++) ops++;  // n each  -> Θ(n log n)

for (int i = 1; i < n; i *= 2)          // log n rounds
    for (int j = 0; j < i; j++) ops++;  // 1 + 2 + 4 + ... < 2n -> Θ(n)

With n = 16, the outer loop takes i = 1, 2, 4, 8 (4 rounds) in both cases:

• first version: 4 rounds × 16 = 64 operations = n log₂ n;
• second version: 1 + 2 + 4 + 8 = 15 operations, less than 2n = 32.

The second one looks like "log n times something", but the "something" is small at the start and only reaches n at the end. A doubling sum is always less than twice its last term.

Best, worst and average case

For a fixed n, different inputs can take different times. Linear search for x in an array of n elements:

• best case: x is at index 0 — 1 comparison, Θ(1);
• worst case: x is last or absent — n comparisons, Θ(n);
• average case (x present, each position equally likely): (1 + 2 + … + n)/n = (n + 1)/2 comparisons — still Θ(n).

Example with the array {7, 3, 9, 4, 1} (n = 5):

Target	Comparisons	Case
7	1	best
9	3	in between
1	5	worst (last)
8	5	worst (absent)

If each of the 5 positions is equally likely, the average is (1 + 2 + 3 + 4 + 5)/5 = 3 = (5 + 1)/2.

Case (which input?) and notation (which bound?) are independent ideas: "the worst case of linear search is Θ(n)" and "the best case is Θ(1)" are both precise statements. Unless told otherwise, analyse the worst case — it is a guarantee.

Space complexity

Space complexity counts the extra memory an algorithm uses besides its input, as a function of n. Reversing an array in place with two indices uses Θ(1) extra space; building a reversed copy uses Θ(n). Recursion is not free: each active call holds a stack frame, so a recursive method that goes n calls deep uses Θ(n) stack space even if it creates no arrays.

Amortized analysis: why ArrayList.add is O(1)

An ArrayList stores its elements in an array. When the array is full, add allocates a larger one and copies every element — a Θ(n) step. Does that make add Θ(n)? Not on average over a sequence of operations.

Worked example. Start with capacity 1 and double when full. Cost of an append = 1 (write the new element) + the number of elements copied.

Append #	Capacity before	Copies	Cost	Capacity after	Total cost so far	3 × appends
1	1	0	1	1	1	3
2	1 (full)	1	2	2	3	6
3	2 (full)	2	3	4	6	9
4	4	0	1	4	7	12
5	4 (full)	4	5	8	12	15
6	8	0	1	8	13	18
7	8	0	1	8	14	21
8	8	0	1	8	15	24
9	8 (full)	8	9	16	24	27

Append 9 alone costs 9 — expensive. But the total after 9 appends is 24, below 3 × 9 = 27. The total always stays below 3n, so the cost per append is below 3 on average: constant.

Aggregate argument. During n appends, copies happen when the size reaches 1, 2, 4, …, up to the largest power of two below n, so the total number of element copies is 1 + 2 + 4 + … + 2ᵏ < 2n. Adding the n writes of the new elements, n appends cost less than 3n steps in total: O(1) amortized per append, even though one individual append can cost Θ(n).

Accounting argument. Charge every append 3 credits: 1 pays for writing the element, 2 are saved "on" it. Just after a resize to capacity 2k, the array holds k elements and no savings. By the time it is full again, k new elements have been appended, saving 2k credits — exactly enough to copy all 2k elements into the next array. The bank balance never goes negative, so 3 credits per operation pay for everything.

The bank balance (3 credits paid minus actual cost) in the example above:

Append #	1	2	3	4	5	6	7	8	9
Cost	1	2	3	1	5	1	1	1	9
Balance after	2	3	3	5	3	5	7	9	3

The balance goes up during cheap appends and drops at each resize, but never below 0.

"Amortized" is not "average case": it is a worst-case guarantee on the total cost of any sequence of operations, spread evenly over them. No probability is involved.

Correctness: loop invariants

Testing can show that a program has bugs; it cannot show that it has none. A loop invariant is a statement about the variables that is true every time the loop condition is checked. You prove it in three steps, like induction:

1. Initialisation — it is true before the first iteration.
2. Maintenance — if it is true before an iteration, it is still true after it.
3. Termination — when the loop stops, the invariant together with the exit condition gives the result you want.

Finding the maximum.

int max = a[0];
for (int i = 1; i < a.length; i++) {
    // Invariant: max == the largest value among a[0..i-1]
    if (a[i] > max) max = a[i];
}

Trace with a = {3, 8, 2, 11, 5}. Check the invariant each time the loop test is reached:

i (at the test)	Part already seen a[0..i−1]	max	Invariant true?
1	{3}	3	yes
2	{3, 8}	8	yes
3	{3, 8, 2}	8	yes
4	{3, 8, 2, 11}	11	yes
5 (loop ends)	{3, 8, 2, 11, 5} — the whole array	11	yes → answer 11

• Initialisation: i = 1, and max = a[0] is the largest of a[0..0].
• Maintenance: if max is the largest of a[0..i−1], after comparing with a[i] it is the largest of a[0..i]; then i increases, so the invariant holds again.
• Termination: the loop stops when i = n, so max is the largest of a[0..n−1] — the whole array.

Binary search.

static int search(int[] a, int target) {    // a sorted in ascending order
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        // Invariant: if target is in a, it is in a[lo..hi]
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;   // everything in a[lo..mid] is < target
        else hi = mid - 1;                   // everything in a[mid..hi] is > target
    }
    return -1;
}

Trace on the sorted array:

index:  0   1   2   3   4   5   6   7   8   9
value:  2   5   8  12  16  23  38  56  72  91

Searching for 23:

Step	lo	hi	mid	a[mid]	Decision
1	0	9	4	16	16 < 23 → lo = 5
2	5	9	7	56	56 > 23 → hi = 6
3	5	6	5	23	found, return 5

Searching for 40 (absent):

Step	lo	hi	mid	a[mid]	Decision
1	0	9	4	16	16 < 40 → lo = 5
2	5	9	7	56	56 > 40 → hi = 6
3	5	6	5	23	23 < 40 → lo = 6
4	6	6	6	38	38 < 40 → lo = 7
end	7	6			lo > hi: range empty, return −1

At every row, 40 (if it were there) would lie in a[lo..hi]; when the range is empty, the invariant says it is not in the array.

• Initialisation: a[lo..hi] is the whole array.
• Maintenance: because the array is sorted, the half that is discarded cannot contain target.
• Termination: either target is found, or lo > hi, the range a[lo..hi] is empty, and by the invariant target is not in the array.

The range shrinks by at least half each time (the + 1 / - 1 guarantee progress), so there are at most ⌊log₂ n⌋ + 1 iterations: Θ(log n) in the worst case. For n = 10 that is at most 4 — exactly what the search for 40 used. Writing lo = mid instead of lo = mid + 1 keeps the invariant true but loses progress — the loop can spin for ever. Correctness needs both an invariant and termination.

Why empirical timing can mislead

Timing experiments are useful, but they are easy to misread:

• Small inputs hide the growth rate. An n² algorithm with a small constant can beat an n log n one for n = 100, and lose badly for n = 10⁶.
• The JVM warms up. The first calls run in the interpreter; later calls run JIT-compiled code, sometimes 10–50 times faster.
• Noise. Garbage collection, other processes, caches and CPU frequency changes all perturb single measurements.
• The input matters. A sorted or random input can hit the best case, not the worst.

A sound experiment doubles n several times and looks at the ratio of times: about 2 for Θ(n), a little over 2 for Θ(n log n), 4 for Θ(n²), 8 for Θ(n³). Counting operations, as in this chapter's labs, gives the same insight without any noise.

For example, if a method takes 10 ms, 40 ms and 160 ms for n = 1000, 2000 and 4000, each doubling multiplies the time by 4: it behaves like Θ(n²).

Key takeaways

• Measure algorithms by how the number of steps grows with n, not by seconds on one machine.
• O = at most (ceiling), Ω = at least (floor), Θ = both (tight). Prove them by giving c and n₀; drop constants and lower-order terms.
• Order to know by heart: 1 < log n < n < n log n < n² < n³ < 2ⁿ < n!. When n doubles: log n adds 1, n doubles, n² quadruples.
• Loops in sequence add, nested loops multiply; dependent loops need a sum (n(n − 1)/2 = Θ(n²)); halving or doubling a counter gives log n.
• Do not confuse Θ(log n) (binary search) with Θ(n log n) (merge sort), nor "O" with "worst case".
• Best, worst and average case are about which input; unless told otherwise, give the worst case.
• Doubling an array makes append O(1) amortized (total < 3n for n appends); growing by a constant makes it Θ(n).
• A loop invariant is proved by initialisation, maintenance and termination; the invariant plus the exit condition must give the answer, and the loop must make progress.