Algorithms · Lecture Notes

Chapter 2: Algorithm Complexity

To say which of two algorithms that solve the same problem is better, we need a yardstick. Time in seconds will not do, because it varies from machine to machine. Complexity analysis instead counts the basic operations an algorithm performs and looks at how that count grows as the input grows. These notes begin with the concepts of time and space complexity and distinguish the best, worst, and average cases. They then define the O, Ω, and Θ notations for growth rate and show how the constants are found. The following sections compute the step count of looping code with summation formulas and the running time of recursive code with recurrence relations. The recurrences are solved by unrolling, by recursion trees, and by the Master Theorem. All these tools are applied to six short Java functions (f1–f6), each representing a different growth class. The notes close with a brief look at amortized analysis.

Learning outcomes

Concepts
Define time and space complexity; tell best-, worst-, and average-case analysis apart; count the steps of a piece of code in the RAM model.
Notation
Write the definitions of Big O, Ω, and Θ; prove a bound for a function by finding the constants c and n0; order the common growth classes.
Loop analysis
Compute the iteration counts of single, nested, and multiplicative loops with summation formulas; show how the bound of the inner loop changes the result (f1, f2, f6).
Recursion
Set up a recurrence for recursive code; solve it by unrolling, with a recursion tree, and with the Master Theorem; recognize the recurrences to which the theorem does not apply (f3, f4, f5).
Amortized analysis
Find the cost per operation from the total cost of a sequence of operations and distinguish it from the average case.

2.1The concept of complexity

That an algorithm works correctly is the first requirement, but not the only one. A correct algorithm may finish in a second on an input of a thousand elements and take days on an input of a million. When choosing an algorithm one therefore also asks, “how many resources does it use?” This section explains how that question is measured. What is measured is not seconds but the number of basic operations; and what matters is how this number grows with the input.

2.1.1What is algorithm complexity?

Complexity theory studies the resources an algorithm uses while it runs. Two resources stand out: time and memory. Both depend on the size of the input. Sorting five numbers takes far less time than sorting five million. Resource use is therefore written not as a single number but as a function of the input size.

The input size is usually denoted n. For an algorithm that processes an array, n is the number of elements in the array. For a string algorithm it is the number of characters, and for a graph algorithm the number of vertices and edges. The time requirement is denoted T(n) and the memory requirement S(n). For example, T(n) = 3n + 3 says that the algorithm performs 3n + 3 basic operations on an input of size n.

Definition 2.1

Time complexity is the number of basic operations an algorithm performs on an input of size n, denoted T(n). Basic operations are those that finish in constant time, such as assignment, comparison, arithmetic, and array access.

Space complexity is the amount of memory the algorithm uses in addition to the input, denoted S(n). Local variables, auxiliary arrays, and the space that recursive calls occupy on the call stack all count toward this memory.

The purpose of analysis is not to measure seconds. The purpose is to see how the resource requirement grows as the input grows. The basic question is this: if the input size doubles, what happens to the running time? Does it stay the same, double, quadruple, or get squared? Figure 2.1 shows the answer to this question for several growth classes.

×1O(1)+1 stepO(log n)×2O(n)×4O(n²)×8O(n³)
Figure 2.1: How the step count changes when the input size doubles. For a constant-time algorithm nothing changes (×1). A logarithmic algorithm takes just one more step. The running time of a linear algorithm doubles, that of a quadratic algorithm quadruples, and that of a cubic algorithm grows eightfold.

The factors in the figure come from simple arithmetic. If T(n) = n2, then T(2n) = 4n2 = 4 · T(n). If T(n) = n3, then T(2n) = 8n3. For the logarithm, log2(2n) = log2 n + 1, so the time grows by just one step. This one question alone makes the difference between algorithms plain. When the input grows a thousandfold, a cubic algorithm slows down a billionfold; a logarithmic algorithm works only about ten steps more.

Common mistake

Stating complexity as a single number, for example “this algorithm takes 12 steps.” Twelve steps is true only for a particular input. Complexity is always a function of n: “this algorithm takes 3n + 3 steps, which is 12 steps for n = 3.”

2.1.2Why timing is not enough

The first way that comes to mind to learn the speed of an algorithm is to run it and measure the time. In Java this is done by reading the system clock before and after the run and printing the difference:

long start = System.currentTimeMillis();
linearSearch(a, 10001);  // 10^8 elements
long end = System.currentTimeMillis();
System.out.println("Elapsed: "
    + (end - start) + " ms");

The code measures how many milliseconds a linear search takes on an array of 108 elements. System.currentTimeMillis() returns the current time in milliseconds. The difference between the two readings is the time the search used. This method is called experimental measurement. It gives a real number, but that number has three serious weaknesses.

  • The result depends on the machine. The same code may take 40 ms on a fast processor and 200 ms on an old laptop. In Java the situation is even more tangled. The JIT compiler (just-in-time compiler) translates frequently run code into machine code while the program runs; so the same measurement comes out slow on the first try and fast on later ones. The cache, the operating system's load at that moment, and the time when the garbage collector kicks in also change the result.
  • A single measurement does not predict the future. A search that took 40 ms on 108 elements, how long does it take on 109? The measurement does not say. If the algorithm grows linearly, the time grows tenfold to 400 ms; if it grows quadratically, it grows a hundredfold and reaches 4 seconds. The answer depends on the growth pattern of the algorithm, and a single measurement does not reveal that pattern.
  • The code must already be written. To compare two designs, both have to be coded, tested, and measured under the same conditions. At the design stage, when there is no code yet, no measurement can be made.
machine A: 2nmachine B: 5nn²/4ntime
Figure 2.2: The same linear algorithm grows with different constants on two machines: 2n on machine A and 5n on machine B. A quadratic algorithm (n2/4) is faster than both for small n, but beyond some point overtakes both.

Figure 2.2 makes the second weakness concrete. Machine B is 2.5 times slower than A; but both lines are correct and grow in the same way. The dashed curve belongs to a different algorithm and grows quadratically. On small inputs this algorithm looks faster than the linear algorithm on both machines. The equality n2/4 = 5n holds at n = 20; beyond this point the quadratic algorithm falls behind even the linear algorithm on the slow machine, and the gap keeps widening. A measurement made on small inputs would have led us to pick the wrong algorithm here.

The remedy for these weaknesses is asymptotic analysis. Asymptotic analysis gives the step count as a function of n and looks only at what happens as n grows. It is independent of the machine; it can be done without writing code, from the description of the algorithm alone. Experimental measurement is not worthless: if two algorithms are in the same growth class, only measurement can tell which one is actually faster. The two methods complement each other. First analysis picks the right growth class, then measurement compares the constant factors.

Table 2.1: Experimental measurement compared with asymptotic analysis.
Experimental measurementAsymptotic analysis
What it givesactual time (ms)growth class of the step count
Depends on the machineyesno
Needs codeyesno, a description suffices
Predicts for large inputsnoyes
Sees constant factorsyesno

2.1.3Counting steps and the RAM model

To count in a machine-independent way we imagine a simple, idealized machine. In this machine every basic operation takes exactly one unit of time. Every cell in memory is reached in the same time, whatever its address. Operations run one at a time, in sequence. This abstract machine is called the RAM model (random-access machine). Real computers do not work this way: data in the cache is read many times faster than data in main memory. But the model is accurate enough for finding the growth class, and it makes the calculation much easier.

Let us apply the model to linear search. Linear search looks at the elements of the array one by one from the beginning to the end. When the sought value (target) is found, it returns its index; if the array ends, it returns −1:

for (int i = 0; i < a.length; i++) {
  if (a[i] == target)
    return i;
}
return -1;

For the count we find how many times each operation runs. Consider the worst case: the target is not in the array, so the loop runs to the end. Let the length of the array be n.

  • The assignment i = 0 is performed once when the loop starts.
  • The condition i < a.length is checked at the start of each round. For each value of i from 0 to n − 1 the condition is true; that makes n checks. When i = n the condition is checked once more and turns out false. In all, n + 1 checks are made.
  • The comparison a[i] == target is made once per round: n times.
  • i++ is performed once at the end of each round: n times.
  • return -1 runs once at the very end.
Table 2.2: Step count of linearSearch in the worst case.
OperationHow many times in the worst case?
i = 01
i < a.lengthn + 1
a[i] == targetn
i++n
return -11
Total T(n)3n + 3

The total is T(n) = 1 + (n + 1) + n + n + 1 = 3n + 3. This number carries two kinds of information. The coefficient 3 and the constant +3 depend on what is counted as a step and on the machine. Had the array access and the comparison been counted as two separate operations, the coefficient would have been 4; had the compiler merged the condition check with the increment, it would have been 2. What does not change is that the step count grows in direct proportion to n. When the array doubles in size, the step count roughly doubles too. Asymptotic analysis keeps this unchanging part and discards the rest: T(n) = Θ(n). Here Θ(n) is read as “grows at the same rate as n”; its precise definition is given together with the asymptotic notation.

Common mistake

Thinking the loop condition is checked n times. The condition is checked n + 1 times, counting the final check that ends the loop. This difference does not change the growth class, but it leads to a wrong result in questions that ask for the exact step count.

2.1.4Code trace: linearSearch

Let us verify the count step by step on a small example. The array is a = [4, 7, 2] and the target is 5. Since 5 is not in the array, the worst case occurs; the expected step count is 3 · 3 + 3 = 12.

Table 2.3: Trace of linearSearch([4, 7, 2], 5). The last column is the total step count so far.
StepOperationiResultTotal steps
1i = 0, then 0 < 30condition true2
2a[0] == 504 ≠ 53
3i++, then 1 < 31condition true5
4a[1] == 517 ≠ 56
5i++, then 2 < 32condition true8
6a[2] == 522 ≠ 59
7i++, then 3 < 33condition false, loop ends11
8return -13returns −112

The condition was checked four times (n + 1 = 4), and the comparison and the increment three times each. The total of 12 steps is the value the formula 3n + 3 gives for n = 3. A constant number of operations, three, is spent on each element: one condition check, one comparison, and one increment. As the number of elements grows, this triple is repeated; this is why the time grows linearly. Figure 2.3 shows the last moment of the trace.

a407122i = 3target = 5i = 01i < a.length4a[i] == target3i++3return -11total steps12
Figure 2.3: The end of the trace of linearSearch([4, 7, 2], 5). The loop has ended at i = 3 and return -1 has run. The table shows how many times each operation was performed: the condition 4 times, the comparison 3, the increment 3. The total is 12 steps.

2.1.5Best, worst, and average case

The step count of linear search depends not only on n. In two arrays of the same length, if the target sits in different places, the step counts differ. If the target is in the first cell, the search ends at once; if it is absent, the whole array is scanned. So the question “how many steps does linear search take?” has no single answer. The question must be asked while saying which input is meant. Three measures are used for this.

Definition 2.2

Consider all inputs of size n.

  • Best case: the number of operations of the input that requires the fewest operations among these inputs.
  • Worst case: the number of operations of the input that requires the most.
  • Average case: the expected number of operations under a probability distribution over the inputs.

The three measures do not have the same value. The worst case is the most used, because it gives a guarantee: the algorithm never takes longer than this on any input. In a real-time system, in the control software of an aircraft, or on a web server, this guarantee matters. The best case gives a lower bound, but by itself carries little information. Almost every algorithm is fast on some lucky inputs. The average case can give the most realistic estimate in practice; but to compute it one must know with what probability the inputs arrive. This information is often missing, and if the assumed distribution is wrong, so is the result.

Example 2.1

The array is [7, 3, 9, 4, 8, 1] (n = 6). The number of comparisons of linear search is computed for three cases.

  1. Best case. The target is 7, the first element. It is found at the first comparison: 1 comparison. However long the array is, this number does not change: Θ(1).
  2. Worst case. The target 5 is not in the array. All six elements are examined: 6 comparisons. If the target were the last element (1), 6 comparisons would be needed as well. In general, n comparisons: Θ(n).
  3. Average case. Assume that the target is in the array and is equally likely (1/6) to be at each of the six positions. A target at position k is found with k comparisons. The expected value is (1 + 2 + 3 + 4 + 5 + 6) / 6 = 21 / 6 = 3.5. In general, (1 + 2 + … + n) / n = (n + 1) / 2 comparisons are made. This number is half the worst case, but it still grows linearly with n: Θ(n).
703192438415target 7 → 1 comparison
703192438415target 5 → 6 comparisons, not found
703192438415target 4 → 4 comparisons
Figure 2.4: Three searches on the array of Example 2.1. Top, the best case: the target 7 is in the first cell, 1 comparison. Middle, the worst case: the target 5 is absent, 6 comparisons. Bottom, a search close to the average: the target 4 is found in the fourth cell. Orange cells are elements looked at and passed over; the green cell is the element found.

The result (n + 1)/2 in the average-case computation comes from Gauss's summation formula: 1 + 2 + … + n = n(n + 1)/2. The same formula appears often in loop analysis. The factor 1/2 between the average and the worst case is a constant of the kind that asymptotic analysis discards. This is why the average and worst cases of linear search fall in the same class. It is not so for every algorithm: quicksort takes Θ(n log n) on average but Θ(n2) in the worst case.

Common mistake

Rounding the average number of comparisons to n/2. If the target is equally likely at each position, the average is exactly (n + 1)/2; for n = 6 it is 3.5, not 3. The class is the same, but in questions that want an exact number this difference means a wrong answer.

2.1.6Space complexity

The second resource, as important as time, is memory. Space complexity is usually given for the auxiliary space. The input itself is not counted, because every algorithm has to keep its input somewhere; what we really want to know is how much memory the algorithm asks for on top of that. An algorithm that sums an array with a single total variable uses only a few variables however long the array is. Its auxiliary space is Θ(1).

In recursive code there is a memory item that is easy to overlook. When a method is called, a stack frame is opened on the call stack for its parameters, local variables, and return address. When the method finishes, the frame is removed. As a recursive function calls itself, frames pile up. The largest number of frames on the stack at one time is the depth of the recursion. The auxiliary space is at least this depth.

Table 2.4: Auxiliary space and time of the examples in this chapter.
CodeWhere does the extra memory come from?SpaceTime
f1: a single looponly x and iΘ(1)Θ(n)
creating new int[n]an auxiliary array of n elementsΘ(n)Θ(n)
f3: f3(n−1) + f3(n−1)stack depth nΘ(n)Θ(2n)
f4: f4(n/2) + f4(n/2)stack depth about log2 nΘ(log n)Θ(n)
Merge sortauxiliary array for mergingΘ(n)Θ(n log n)

Table 2.4 shows an important fact: time and space can grow at different rates. The function f3, which calls itself twice with n − 1, makes an exponential number (2n − 1) of calls. Yet its memory is only linear. The reason is that the calls run one after another, not at the same time. f3(n) first calls the left f3(n − 1) and does not move to the right one until all subcalls of this call have finished and their frames have been removed. At any moment the stack holds only one chain: f3(n), f3(n − 1), …, f3(1). The length of this chain is n.

The same reasoning applies to f4. In f4 the input halves with each call, so the chain has the form n, n/2, n/4, …, 1 and its length is about log2 n + 1. For example, while f4(16) runs, the stack holds at most 5 frames (16, 8, 4, 2, 1).

Common mistake

Confusing the memory of a recursive function with the total number of calls. For f3 it is wrong to say “there are 2n calls, each opens a frame, so the memory is Θ(2n).” The frame of a finished call is removed and its space is reused for the next call. The memory is determined by the largest number of frames open at the same time, that is, by the recursion depth.

2.2Asymptotic notation

When the step count came out as 3n + 3, we said that the coefficients would be discarded and only the fact that the growth is “linear” kept. The rules for this “discarding” must be precise; otherwise two people could assign different classes to the same code. Asymptotic notation sets these rules. The word “asymptotic” says that we are concerned with what happens as n goes to infinity. Behavior on small inputs and constant factors are deliberately ignored. Three notations are used: O for an upper bound, Ω for a lower bound, and Θ for a tight bound.

The O notation appeared long before algorithms, at the end of the 19th century, in number theory. Paul Bachmann used it in 1894, and Edmund Landau popularized it. In a short article in 1976, Donald Knuth defined Ω and Θ in their present senses and proposed that the three be used together in the analysis of algorithms. Today all algorithms textbooks use these definitions.

2.2.1Big O

Big O states an upper bound. The statement “f(n) = O(g(n))” says that for every sufficiently large n, f does not exceed a constant multiple of g. Two details matter. First, the constant multiple is free: g may be multiplied by 4 or by 100. Second, small n are irrelevant: it is enough for the inequality to hold beyond a threshold value.

Definition 2.3

f(n) = O(g(n)) if and only if there exist a positive constant c and a threshold n0 such that for every n ≥ n0

0 ≤ f(n) ≤ c · g(n)

holds. In this case g is an upper bound for f. The notation is called Big O notation.

The definition has two constants, and each has its own job. c swallows constant factors. The factor-of-3 difference between 3n2 and n2 disappears by choosing c = 3. n0 leaves out small inputs. The function n2 + 100 is larger than 2n2 at n = 1; but once n ≥ 10 it does not exceed it. Because the definition is concerned only with what comes after n0, such differences at the start do not affect the result.

An example: the function f(n) = 3n2 + 5n + 2 is O(n2). Indeed, with c = 4, 3n2 + 5n + 2 ≤ 4n2 holds for every n ≥ 6. How these constants are found is shown step by step a little further down. Figure 2.5 shows the situation on a graph.

02468100100200300400nn₀ = 6f(n)4n²
Figure 2.5: f(n) = 3n2 + 5n + 2 (blue) and 4n2 (red). For small n, f is on top. The curves cross at n ≈ 5.37. After n0 = 6, f always stays below 4n2; hence f(n) = O(n2).

Because Big O is an upper bound, it can also be loose. 3n2 + 5n + 2 is O(n2), and also O(n3) and O(2n); all these statements are true. But their information value is not the same. The sentence “this algorithm runs in O(2n) time” is true but misleading for a quadratic algorithm. In analysis one usually gives the smallest upper bound that can be found.

The equals sign in the notation is also open to misunderstanding. f(n) = O(g(n)) actually means “f belongs to the set of functions bounded above by a constant multiple of g.” The statement is therefore one-directional. n = O(n2) is true; but it does not follow that “O(n2) = n.” For this reason some books write f(n) ∈ O(g(n)).

Common mistake

Saying “Big O represents the worst case.” Big O is a kind of bound; the worst case is a kind of input. The two are independent. An upper bound can be written for the worst-case running time, for the best-case running time, and for the average running time. “The best case of linear search is O(1)” is a valid sentence. The source of the confusion is that in practice Big O is mostly used for the worst-case running time.

2.2.2Big Omega and Big Theta

The opposite of an upper bound is a lower bound. To say that an algorithm takes “at least this much,” Ω (Big Omega) is used. If the two bounds meet at the same function, the growth rate is known exactly; Θ (Big Theta) expresses this.

Definition 2.4

f(n) = Ω(g(n)): there exist c > 0 and n0 such that for every n ≥ n0, f(n) ≥ c · g(n) ≥ 0. In this case g is a lower bound for f.

f(n) = Θ(g(n)): there exist c1, c2 > 0 and n0 such that for every n ≥ n0, c1 · g(n) ≤ f(n) ≤ c2 · g(n). In this case g is a tight bound for f.

Table 2.5: The three asymptotic notations. In the definitions we look for positive constants for which the inequality holds for every n ≥ n0.
NotationMeaningDefinitionAnalogue for numbers
f = O(g)upper boundf(n) ≤ c · g(n)f ≤ g
f = Ω(g)lower boundf(n) ≥ c · g(n)f ≥ g
f = Θ(g)tight boundc1 · g(n) ≤ f(n) ≤ c2 · g(n)f = g

The last column of the table is a handy analogy: O behaves like “less than or equal,” Ω like “greater than or equal,” and Θ like “equal.” The analogy also recalls the basic relation: a number that is both ≤ g and ≥ g equals g. In the same way,

f = Θ(g) ⇔ f = O(g) and f = Ω(g).

Θ means squeezing between two constant multiples. Figure 2.6 shows this on 3n2 + 5n + 2: for n ≥ 6 the function stays between 3n2 and 4n2. It is therefore Θ(n2). Although the same function is O(n3), it is not Θ(n3). Every lower curve of the form c · n3, however small c is chosen, overtakes the function at some point. This is because the ratio f(n)/n3 tends to zero as n grows.

02468100100200300400nn₀ = 6f(n)4n²3n²
Figure 2.6: The squeezing meaning of Θ. For n ≥ 6, f(n) = 3n2 + 5n + 2 (blue) is bounded below by 3n2 (green) and above by 4n2 (red).

The distinction between growth class and case must be made once more here. For linear search all of the following sentences are true: the worst-case running time is Θ(n); the best-case running time is Θ(1); over all inputs the running time is O(n) and Ω(1). But the sentence “linear search is Θ(n)” is incomplete unless it says which case is meant. Insertion sort is similar: it takes Θ(n2) in the worst case and Θ(n) on sorted input; a single Θ cannot be written for all inputs. Merge sort, on the other hand, takes Θ(n log n) on every input; for it, writing Θ without naming a case is correct.

Common mistake

Using Θ and O interchangeably. “3n2 + 5n + 2 = Θ(n3)” is wrong; what is correct is O(n3). Θ requires both a lower and an upper bound and gives the growth rate of the function exactly. In everyday speech, “this algorithm is O(n2)” often means Θ(n2); in a written analysis this distinction should be kept.

2.2.3Finding the constants

Proving a bound means finding the constants in the definition concretely. The method is the same every time: choose a c, solve the inequality, and find from which n on it holds. The constants are not unique; any valid pair suffices for a proof.

Example 2.2

We show that f(n) = 3n2 + 5n + 2 = Θ(n2). For this two inequalities are needed: an upper bound and a lower bound.

  1. Choosing c2 for the upper bound. Since the leading coefficient is 3, a number slightly larger than 3 is tried: c2 = 4. The desired inequality is 3n2 + 5n + 2 ≤ 4n2.
  2. Solving the inequality. Everything is collected on one side: n2 − 5n − 2 ≥ 0. The positive root of the quadratic equation is (5 + √33)/2 ≈ 5.37. The inequality holds for n larger than this root. Since the smallest integer is 6, n0 = 6.
  3. Checking the bound. At n = 5 the left side is 75 + 25 + 2 = 102 and the right side is 100; the inequality fails. At n = 6 the left side is 108 + 30 + 2 = 140 and the right side is 144; the inequality holds.
  4. Seeing that it keeps holding. When n increases by one, the left side grows by 6n + 8 and the right side by 8n + 4. For n ≥ 6, 8n + 4 > 6n + 8, so the right side grows more at every step. The gap (4) that opened at n = 6 therefore never closes; it only grows.
  5. The lower bound. Choose c1 = 3. The inequality 3n2 + 5n + 2 ≥ 3n2 is true for every n ≥ 1 because 5n + 2 > 0.
  6. Combining. Together the two inequalities hold for n ≥ 6: 3n2 ≤ f(n) ≤ 4n2. With c1 = 3, c2 = 4, n0 = 6 the definition is satisfied: f(n) = Θ(n2).
Table 2.6: Comparison of f(n) = 3n2 + 5n + 2 with 4n2.
nf(n)4n2f(n) ≤ 4n2?
1104no
34436no
5102100no
6140144yes
7184196yes
8234256yes

To see that the constants are not unique, another choice can be made. If c2 = 10 is chosen, then already at n = 1, 3 + 5 + 2 = 10 ≤ 10. Also, for every n ≥ 1, 5n ≤ 5n2 and 2 ≤ 2n2, so one can write 3n2 + 5n + 2 ≤ 3n2 + 5n2 + 2n2 = 10n2. This proof does not require computing the root: each term is bounded by the largest power and the coefficients are added. A large c means a small n0; a small c requires a larger threshold.

The same method applies to a linear function. To show that 2n + 10 = O(n), choose c = 3; then 2n + 10 ≤ 3n holds for n ≥ 10: c = 3, n0 = 10. With the term-by-term bounding method one writes 2n + 10 ≤ 2n + 10n = 12n, which gives c = 12, n0 = 1.

It is also possible to show that a bound is wrong. For this one proves that no pair of constants works, usually by contradiction. Suppose n2 = O(n). Then for some c and n0, for every n ≥ n0 we must have n2 ≤ c · n, that is, n ≤ c. But n can be chosen larger than both n0 and c, for example n = max(n0, ⌈c⌉ + 1). For this n, n ≤ c fails. Since the assumption leads to a contradiction, it is false: n2 ≠ O(n).

Common mistake

Trying only a single value of n in a proof. “At n = 10, f(10) ≤ 4 · 100, so it is O(n2)” is insufficient. The definition requires the inequality to hold for every n beyond n0. One has to solve the inequality algebraically or bound each term by the largest power.

2.2.4Rules of calculation

Searching for constants every time is laborious. A few rules that follow from the definitions often let us read off the class directly.

  • Constant factors are dropped. c · f(n) = Θ(f(n)); for example 5n = Θ(n) and n2/3 = Θ(n2). The constant factor is absorbed into the c of the definition.
  • Lower-order terms are dropped. In a polynomial the term with the largest power remains: 4n3 + 100n2 + 7 = Θ(n3). As n grows, 100n2 becomes negligible next to 4n3; at n = 1000 it is about a fortieth of it.
  • Sum rule: sequential code. The total running time of two pieces of code that run one after the other is the running time of the larger: O(f) + O(g) = O(max(f, g)). If a loop that takes Θ(n) is followed by a loop that takes Θ(n2), the total is Θ(n2).
  • Product rule: nested code. If a loop that runs n times contains work that takes O(g), the total is O(n · g). The rule assumes that the inner work is the same in every round. If the running time of the inner work depends on the counter of the outer loop, a sum is computed instead of a product.
  • The base of a logarithm is irrelevant. By the change-of-base formula, loga n = logb n / logb a. The difference between two bases is only a constant factor. This is why one writes O(log2 n) = O(log10 n) = O(log n) and often does not state the base.
  • In exponentials the base matters. 3n = O(2n) is false. The ratio 3n/2n = 1.5n goes to infinity; no constant factor can close this gap. Unlike logarithms, exponential bases are not related by a constant factor.

As a consequence of these rules, the common functions fall into a definite order of growth:

1 < log n < √n < n < n log n < n2 < n3 < 2n < n!

Here the sign “<” says that the one on the left becomes negligible relative to the one on the right: for large n the ratio goes to zero. For example the ratio log n / √n approaches zero, though slowly at first.

Common mistake

Leaving constants and small terms in the result: writing O(3n + 3) or O(n2/3 + n). These expressions are not wrong, but they go against the purpose of the notation. The correct forms are O(n) and O(n2). Similarly one writes O(2n) instead of O(2n+1), since 2n+1 = 2 · 2n; but 22n = 4n is not O(2n).

2.2.5Common growth classes

A very large share of algorithms fall into one of a few growth classes. Which class an algorithm belongs to tells at once how it will behave as the input grows. Table 2.7 lists these classes from fastest to slowest. The last column shows which class each of the six example functions of this chapter falls into.

Table 2.7: Common growth classes.
ClassNameTypical exampleWhen n doublesIn this chapter
O(1)constantarray access, printing the first elementunchanged—
O(log n)logarithmicbinary search, fast exponentiation, Euclid's algorithm+1 stepf6 (upper bound)
O(√n)square-rootprimality testing by trial division≈ 1.41 times—
O(n)linearlinear search, largest element, sum of an array2 timesf1, f4
O(n log n)linearithmicmerge sort, heap sort, quicksort (average)slightly more than 2 timesf5
O(n2)quadraticbubble, selection, and insertion sort4 times—
O(n3)cubicclassical matrix multiplication8 timesf2
O(2n)exponentialall subsets, naive recursive Fibonaccisquaredf3
O(n!)factorialall permutationsexplodes much faster—

The “when n doubles” column of the table is the shortest way to convey the difference between the classes. In a logarithmic algorithm only one step is added when the input doubles; this is why binary search finishes with about thirty comparisons even on a billion elements. For the square root the factor is √2 ≈ 1.41. For linearithmic the factor is slightly more than 2: 2n log(2n) = 2n log n + 2n. In the exponential class the situation is entirely different: since 22n = (2n)2, the time is squared. A computation of 2n steps that takes 1 second on a computer performing 109 operations per second (n ≈ 30) takes about 36 years when the input doubles.

There is one more important line between the classes. Classes of the form nk are called polynomial time; they are generally regarded as “efficient.” The exponential and factorial classes are regarded as “inefficient”; beyond small inputs they cannot be run in practice. This distinction is a rough rule (n100 is a polynomial but not at all efficient), yet it still guides algorithm design.

A note is needed on f6 in the “In this chapter” column of the table. It is true that f6 is O(log n), but this bound is not tight. The true class of f6 is log* n, which grows even much more slowly than the logarithm. This interesting function is examined in detail in the section on loop analysis.

2.2.6Growth curves and numbers

The order of the classes can also be seen on a graph. Figure 2.7 plots five functions for n from 1 to 20. For small n the curves are close together; at n = 4, n2 and 2n are even equal (both are 16). After n = 5, 2n pulls ahead and rapidly moves away. The curve 2n exceeds 100 at n ≈ 6.6; n2 exceeds it only after n = 10. n log2 n stays close to linear, and log2 n is nearly flat.

051015200255075100nstepslog₂ nnn log₂ nn²2ⁿ
Figure 2.7: log2 n, n, n log2 n, n2, and 2n for n from 1 to 20. The vertical axis is cut off at 100 steps; 2n and n2 soon exceed this limit.

The difference in the graph is even more striking in numbers. Table 2.8 shows how long each class takes on a computer that performs 109 basic operations per second. The values were computed by dividing the operation count by 109.

Table 2.8: Approximate running times on a computer performing 109 operations per second.
f(n)n = 10n = 20n = 50n = 100n = 106
log2 n3.3 ns4.3 ns5.6 ns6.6 ns19.9 ns
n10 ns20 ns50 ns100 ns1 ms
n log2 n33 ns86 ns282 ns664 ns19.9 ms
n2100 ns400 ns2.5 µs10 µs16.7 minutes
n31 µs8 µs125 µs1 ms31.7 years
2n1 µs1 ms13 days4 · 1013 years—
n!3.6 ms77 years1048 years3 · 10141 years—

The table says two things. First, the polynomial classes remain reasonable even on a million elements; the quadratic algorithm takes 17 minutes and the cubic algorithm more than thirty years. Second, the exponential and factorial classes become unrunnable even on very small inputs. For n = 100, 2n steps take three thousand times the age of the universe (about 1.4 · 1010 years).

The interactive calculator in the slides produces the same table for any desired n; the “n × 2” button doubles the input. When the button is pressed, the n column doubles, the n2 column quadruples, and the n3 column grows eightfold; log2 n rises by only 1, and 2n squares itself. The lesson is this: a computer ten times faster buys a constant factor, while a better algorithm changes the growth class. An algorithm that takes n log n instead of n2 reduces a 17-minute job to 20 milliseconds at n = 106; no hardware improvement gains that much.

2.3Loop analysis

A piece of code without loops and without recursion performs a constant number of operations; its running time is Θ(1). What ties the running time to the input is loops and recursion. This section deals with loops. The method can be stated in one sentence: find how many rounds each loop runs, and for nested loops add up these round counts. The method is applied to three example functions: f1 with a single loop, f2 whose inner loop bound depends on the outer counter, and f6 whose counter grows at an unusual rate.

The six example functions of this chapter share a trick: each returns a counter x that increases with the work done. The return value thus becomes the step count itself. The formula found by analysis can be checked directly by running the function and looking at the return value. All the return values and call counts given in these notes were obtained by running the code in Java.

2.3.1f1: a single loop

public int f1(int n) {
  int x = 0;
  for (int i = 0; i < n; i++) {
    x++;
  }
  return x;
}

The code has three parts.

  • Initialization: the line int x = 0; assigns 0 to x. This is a single operation, independent of the input: O(1).
  • The loop: in the header for (int i = 0; i < n; i++), i starts at 0, increases by one each round, and goes up to n − 1. The values 0, 1, …, n − 1 number n; the loop runs n rounds.
  • The body: x++; runs once per round and is a constant-time operation: O(1).

By the product rule, a loop that runs n times doing O(1) work per round does n · O(1) = O(n) work in total. The initialization and the return outside the loop are constant work; by the sum rule they do not change the result:

T(n) = O(1) + n · O(1) = Θ(n)

Since the body runs exactly n times, the lower bound is also n; the result is therefore written with Θ. The function returns x = n: f1(16) = 16, f1(32) = 32. The return value is the step count itself, and it doubles when the input doubles. This is the signature of linear growth.

2.3.2Code trace: f1(4)

Let us trace f1 for n = 4. On each line the value of the condition and the new value of x are written.

Table 2.9: Trace of f1(4).
StepiCondition i < 4x (after the body)
start——0
round 10true1
round 21true2
round 32true3
round 43true4
exit4falsereturns 4

The condition was checked five times (n + 1) and the body ran four times (n). These counts have the same form as the count in linear search. Since the body runs exactly n times, the result Θ(n) is visible in the trace too. Figure 2.8 shows the final state of the trace.

0i=01i=12i=23i=3x++ count: 4
Figure 2.8: The end of f1(4). Each box is a loop round; all four rounds, i = 0, 1, 2, 3, have been completed and x++ has been executed four times.

2.3.3f2: nested loops

public int f2(int n) {
  int x = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i * i; j++) {
      x++;
    }
  }
  return x;
}

In f2 two loops are nested. The outer loop is like the one in f1: i goes from 0 to n − 1 and runs n rounds. The bound of the inner loop, however, is not constant. j goes from 0 to i · i − 1; that is, in the current round of the outer loop the inner loop runs i2 times. At i = 0 the inner loop does not run at all, at i = 1 it runs once, at i = 2 four times, at i = 3 nine times.

Because the number of rounds of the inner loop depends on the current value of i, the product rule cannot be applied directly. To say “the outer loop runs n rounds, the inner loop n rounds, total n · n” is wrong, because the inner loop runs a different number of times in each round. The right way is to write down the inner round count for each outer round and add them up:

T(n) = 02 + 12 + 22 + … + (n − 1)2 = Σi=0n−1 i2

Common mistake

Automatically counting two nested loops as O(n2). The result is determined by the bound of the inner loop. In f2 the bound is i2, so the result is of order n3. With the bound j < i it would be quadratic, with j < 10 linear. If the outer loop advanced with i *= 2, the result would again come out different.

2.3.4Code trace: f2(4) and f2(5)

In the call f2(4) the outer loop runs four rounds (i = 0, 1, 2, 3). Table 2.10 shows the value of x after each outer round. The values were verified by running the code in Java.

Table 2.10: Trace of f2(4).
iInner loop conditionInner roundsx (after the round)
0j < 000
1j < 111
2j < 445
3j < 9914
4outer condition 4 < 4 false—returns 14

The round i = 0 is interesting: the condition of the inner loop is j < 0 · 0, that is, 0 < 0, which is false at the first check. The inner loop does not run at all, but the outer round still counts. The result is 0 + 1 + 4 + 9 = 14. Figure 2.9 shows the rounds as boxes, row by row: row i has i2 boxes.

i=00 roundsi=11 roundi=24 roundsi=39 roundsx = 14
Figure 2.9: The rounds of the inner loop in f2(4). Each row is an outer round and each box is an x++. The rows have lengths 0, 1, 4, 9; total 14.

On a slightly larger input the pattern becomes clearer. In f2(5) the outer loop runs one more round, and at i = 4 the inner loop runs 16 times. The total is 0 + 1 + 4 + 9 + 16 = 30. Figure 2.10 shows each outer round as a bar. The bar heights are i2 and the total area is the number of x++ the function performs. The last bar alone makes up more than half of the total: the last rounds dominate.

0² = 0i=01² = 1i=12² = 4i=23² = 9i=34² = 16i=4total x++ = 30
Figure 2.10: The number of inner rounds in each outer round of f2(5). The bars have heights 0, 1, 4, 9, and 16; their sum is 30 and f2(5) returns 30.

2.3.5Computing the sum

There is a closed formula for the sum of consecutive squares:

Σi=0n−1 i2 = (n − 1) · n · (2n − 1) / 6 = (2n3 − 3n2 + n) / 6

The formula can be checked with small values. For n = 5 it gives 4 · 5 · 9 / 6 = 30, the total in the trace. For n = 4 it gives 3 · 4 · 7 / 6 = 14. In the expanded form the dominant term is 2n3/6 = n3/3. Dropping the constant 1/3 and the lower-order terms gives the result:

T(n) = Θ(n3)

Table 2.11: The return value of f2(n) compared with n3/3 (measured in Java).
nf2(n)n3/3
41421
53042
161,2401,365
3210,41610,923

The two columns in the table approach each other as n grows. At n = 4 the ratio is 14/21 ≈ 0.67, while at n = 32 it is 10,416/10,923 ≈ 0.95. The lower-order term −3n2/6 matters at small n and loses its importance at large n. A further sign of cubic growth is the doubling test. When n goes from 16 to 32, the return value grows by a factor of 10,416 / 1,240 = 8.4. This number is close to 23 = 8; as n grows, the ratio gets closer still to 8.

The result in this section is an example of a general rule: Σi<n ik = Θ(nk+1). If the round count of the inner loop is the k-th power of the outer counter, the total work goes up by one degree. The rule comes from the sum resembling an integral: ∫0n xk dx = nk+1/(k + 1). For f2, k = 2 and the integral gives n3/3, the same as the dominant term in the exact formula.

2.3.6Loop patterns and summation formulas

In loop analysis a few patterns come up again and again. Each reduces to a known series: an arithmetic series, a sum of squares, or a geometric series. Table 2.12 collects these patterns. The round counts were checked by counting in Java for n = 16 and n = 20.

Table 2.12: Frequently encountered loop patterns.
PatternRound countn = 16Result
for (i = 0; i < n; i++)Σ 1 = n16Θ(n)
for (j = 0; j < n; j++) inside i < nn · n256Θ(n2)
for (j = 0; j < i; j++) inside i < nΣ i = n(n − 1)/2120Θ(n2)
for (j = 0; j < i * i; j++) inside i < nΣ i2 = (n − 1)n(2n − 1)/61,240Θ(n3)
for (i = 1; i < n; i *= 2)⌈log2 n⌉4Θ(log n)
j < n inside for (i = n; i > 0; i /= 2)n · (⌊log2 n⌋ + 1)80Θ(n log n)
j < i inside for (i = 1; i < n; i *= 2)1 + 2 + 4 + … < 2n15Θ(n)
for (i = 0; i < n; i = 1 << i) (f6)log* n + 14Θ(log* n) (mathematical model; in Java, n ≤ 65536)

The third row of the table is a lower-degree sibling of f2. The inner loop runs i times; the total is 0 + 1 + … + (n − 1) = n(n − 1)/2. This number is about half of n · n; since the difference is a constant factor, the class is still Θ(n2). This pattern is the reason selection sort and insertion sort are quadratic.

The fifth row is a multiplicative loop. i doubles in each round: 1, 2, 4, 8, …. After k rounds i = 2k. The loop continues while 2k < n; it stops when k ≥ log2 n. The round count is therefore ⌈log2 n⌉. At n = 16, i takes the values 1, 2, 4, 8 and the loop runs 4 rounds; at n = 1000 it runs 10 rounds, from 1 to 512. Every loop whose counter grows or shrinks by a constant ratio is logarithmic.

In the sixth row the outer loop is logarithmic and the inner loop is linear. The bound of the inner loop does not depend on the outer counter; it runs exactly n times in every round. The product rule therefore applies: (⌊log2 n⌋ + 1) · n. For n = 16 the outer loop runs 5 rounds, at i = 16, 8, 4, 2, 1; the total is 5 · 16 = 80.

The seventh row is surprising. On the surface its structure resembles the previous one: a logarithmic outer loop with an inner loop inside it. But the bound of the inner loop is i, and i grows quickly. The total is a geometric series:

1 + 2 + 4 + … + 2k = 2k+1 − 1 < 2n

Here 2k is the largest power of two smaller than n; hence 2k+1 < 2n. Although the outer loop runs log n times, the total work is linear. At n = 16, 1 + 2 + 4 + 8 = 15 rounds are made. This is the property of a geometric series: the sum is determined by its last term, and the last term is larger than the sum of all the earlier ones.

Example 2.3

Find the number of x++ executions and the growth class of the following two pieces of code.

// first part
for (int i = 1; i < n; i *= 2)
  for (int j = 0; j < i; j++)
    x++;

// second part
for (int i = n; i > 0; i /= 2)
  for (int j = 0; j < n; j++)
    x++;
  1. First part. i takes the values 1, 2, 4, …, 2k < n. In each round the inner loop runs i times. The total is 1 + 2 + … + 2k = 2k+1 − 1 < 2n: Θ(n). For n = 16, x++ is executed 15 times.
  2. Second part. The outer loop runs ⌊log2 n⌋ + 1 rounds, at i = n, n/2, n/4, …, 1. The inner loop runs n times in each round, because its bound is n. The total is n · (⌊log2 n⌋ + 1): Θ(n log n). For n = 10, i = 10, 5, 2, 1 and x++ is executed 4 · 10 = 40 times.

The outer loops of the two parts run a similar number of rounds; the difference comes from the bound of the inner loop. If the bound depends on the outer counter, the round counts are added; if it does not, they are multiplied.

Common mistake

Always counting an inner loop inside a logarithmic outer loop as Θ(n log n). The first part of the example above is only Θ(n), although the outer loop runs log n times. One does not decide without writing down the inner round count for each outer round and adding them up.

2.3.7f6: a loop with a shifting bound

public static int f6(int n) {
  int x = 0;
  // 1 << i equals 2^i (overflow is ignored)
  for (int i = 0; i < n; i = 1 << i) {
    x++;
  }
  return x;
}

At first sight the loop of f6 resembles a multiplicative loop, but its update is different.

  • Initialization: int i = 0; is a constant-time assignment.
  • Condition: i < n checks at the start of each round whether i is smaller than n.
  • Update: i = 1 << i. The left-shift operator << shifts the bits of the number 1 to the left by i places. In binary, shifting 1 to the left by i places multiplies it by 2i. The result is 2i, computed in a single operation, in constant time.

The critical point is this: the update is not i = 2 * i but i = 2i. In a multiplicative loop i doubles in each round. In f6, i itself becomes the exponent. This makes i grow much faster: the value 4 becomes not 8 in the next round but 24 = 16. And 16 becomes not 32 but 216 = 65,536.

2.3.8Code trace: f6(20)

Table 2.13: Trace of f6(20).
RoundiCondition i < 20xNext i = 1 << i
10true11 << 0 = 1
21true21 << 1 = 2
32true31 << 2 = 4
44true41 << 4 = 16
516true51 << 16 = 65,536
—65,536falsereturns 5—

The loop runs only five rounds. The values taken by i are 0, 1, 2, 4, 16; the next value is 65,536, so the loop ends. Figure 2.11 shows this chain. The same loop also runs five rounds for n = 65,536; although n has grown more than three thousandfold, the round count does not change.

01241665536values of i (n = 20); i ← 1 << icondition: 65536 < 20 → false, loop ends
Figure 2.11: The values taken by i in f6(20): 0 → 1 → 2 → 4 → 16 → 65,536. The last value fails the condition (65,536 < 20 is false) and the loop ends after five rounds.

2.3.9How many rounds does f6 really run?

The values of i in f6 grow like a tower of powers of two:

0 → 20 = 1 → 21 = 2 → 22 = 4 → 24 = 16 → 216 = 65,536 → 265,536

The last value is a number with 19,729 digits. The number of atoms in the universe is estimated at about 1080; next to this number, 1080 is tiny. Since no real input can be that large, f6 runs at most six rounds for any n one can imagine.

A common line of reasoning for this loop goes: “after k rounds i ≥ 2k; the loop stops when 2k ≥ n; so k ≈ log2 n and the time is O(log n).” The reasoning is correct for the loop i = 2 * i. For f6 the result is not wrong either, because i at least doubles, so the round count cannot exceed log2 n. But this bound is not tight. In f6, after k rounds i is a tower of height k − 1, and the round count is given by a function that grows much more slowly.

Definition 2.5

The iterated logarithm log* n gives the number of times log2 must be applied to n in succession until the result is less than or equal to 1. For example, since log2 16 = 4, log2 4 = 2, log2 2 = 1, we have log* 16 = 3.

The round count of f6 is exactly log* n + 1. This equality was checked for every value from n = 1 to 70,000 with a Python script. log* n does not exceed 5 for any input one can imagine: log* 65,536 = 4, and to reach 5, n must exceed 65,536. The smallest number with value 6 is larger than 265,536. This function, which behaves like a constant in practice, also appears in the analysis of the union-find data structure.

Table 2.14: The return value of f6(n) compared with ⌈log2 n⌉ (measured in Java).
nf6(n)⌈log2 n⌉log* n
4322
16443
32554
1,0005104
65,5365164

For small n, f6 and ⌈log2 n⌉ are close together; at n = 32 both are 5. As n grows, the logarithm keeps increasing while f6 stays at 5. Conclusion: O(log n) is a correct upper bound, but the tight bound is Θ(log* n).

The comment line in the code of f6 says “overflow is ignored.” This assumption matters in Java. In Java an int has 32 bits, and the shift operator uses only the low five bits of the shift amount; that is, it takes the amount modulo 32. Since 65,536 = 32 · 2048, 1 << 65536 is the same as 1 << 0 and gives 1. So for n > 65,536, i enters the cycle 0, 1, 2, 4, 16, 65,536, 1, 2, 4, 16, 65,536, …; the condition never becomes false and f6 never terminates. This behavior was observed with a copy run at n = 100,000 with the round count capped. The result Θ(log* n) in the analysis holds for an abstract machine with unbounded integers.

Common mistake

Confusing a shift with a multiplication. The update i = 1 << i is i = 2i, not i = 2 * i. The latter is written i <<= 1 or i = i << 1. If the shifted number and the shift amount trade places, the round count of the loop changes between log n and log* n.

2.4Analysis of recursion

In looping code the round counts are added. In recursive code, the running time depends on the running time of the same function on smaller inputs. To find T(n), values such as T(n − 1) or T(n/2) are needed first. The equation that expresses this relation is called a recurrence relation. This section explains how the relation is set up and the most basic solution method, unrolling.

2.4.1The recurrence relation

Definition 2.6

A recurrence relation is an equation that defines T(n) in terms of the values of T on smaller inputs. For the running time of a recursive function, the general form is:

T(n) = (running times of the subcalls) + (work done outside the calls), T(base) = Θ(1)

The second equation gives the running time of the base case, which the recursion solves directly without calling itself.

To set up the relation, three questions are asked of the code:

  1. How many recursive calls are there? This number becomes the coefficient of T in the relation.
  2. By how much does the input of each call shrink? If the input decreases by one, write T(n − 1); if it halves, write T(n/2).
  3. How much work is done outside the calls? The running time of work such as splitting, merging, and adding enters the relation as an additional term.
T(n)+ f(n): work outside the callsT(n/b)T(n/b)T(n/b)…a calls, each of size n/b (or n − 1)
Figure 2.12: The structure of a recursive call. A call that takes T(n) starts a subcalls; each works with a smaller input (n/b or n − 1). The work the call itself does is f(n).

Once the relation is set up, it has to be solved; that is, a closed form of T(n) not containing T is found. There are three methods:

  • Unrolling (substitution): the relation is substituted into itself repeatedly, a pattern is found, and when the base case is reached the terms are added up. Used for f3.
  • Recursion tree: each call is drawn as a node, the work at each level is added up, and then the level sums are added. Used for f3, f4, and f5.
  • Master Theorem: gives a ready-made result for relations of the form T(n) = aT(n/b) + f(n). Used for f4 and f5.

2.4.2f3: two calls, n − 1

public long f3(int n) {
  if (n <= 1) {
    return 1;
  }
  return f3(n - 1) + f3(n - 1);
}

f3 has two parts.

  • Base case: when n ≤ 1 the function returns 1. This is constant-time work: T(1) = c.
  • Recursive case: when n > 1, f3(n − 1) is called twice and the results are added. The addition and the comparison are constant work; this too is called c.

Once the three questions are answered, the relation emerges: there are two calls, each of size n − 1, and constant work is done outside the calls.

T(n) = 2T(n − 1) + c, n > 1;  T(1) = c

The input shrinks by only one in each call, but the number of calls doubles at every level. f3(4) calls two f3(3); each f3(3) calls two f3(2); each f3(2) calls two f3(1). The levels have 1, 2, 4, 8 calls, and the total is 1 + 2 + 4 + 8 = 15 = 24 − 1 (Figure 2.13).

f3(4)1 callf3(3)2 callsf3(2)4 callsf3(1)8 callsinput shrinks by 1, calls double: 1 + 2 + 4 + 8 = 15 = 2⁴ − 1
Figure 2.13: The levels of f3(4). The input shrinks by one at each level while the number of calls doubles: 1, 2, 4, 8. In all, 15 = 24 − 1 calls.

This relation is not of the form T(n/b); the subproblem shrinks not by division but by subtracting one. The Master Theorem therefore does not apply, and the relation is solved by unrolling.

2.4.3Code trace: f3(3)

In tracing recursive code, the order in which calls start and end matters. The steps of the call f3(3) are as follows; the indentation shows the depth of the call. The order was verified with a copy run in Java that prints the start and end of every call.

Table 2.15: Trace of f3(3). The last column is the number of calls started so far.
StepEventStack (bottom to top)Calls
1f3(3) is called; 3 > 1, not the base casef3(3)1
2the left f3(2) is calledf3(3) f3(2)2
3f3(1): base case, returns 1f3(3) f3(2) f3(1)3
4second f3(1): returns 1f3(3) f3(2) f3(1)4
5f3(2) = 1 + 1 = 2 returnsf3(3)4
6the right f3(2) is called; the same work is done again from scratchf3(3) f3(2)5
7two f3(1), each returns 1f3(3) f3(2) f3(1)7
8the second f3(2) = 2 returnsf3(3)7
9f3(3) = 2 + 2 = 4 returnsempty7

The trace shows three things. In all 7 = 23 − 1 calls were made. The stack held at most three frames at the same time; this is the depth, which equals n. Third and most important, the right f3(2) repeats exactly the work the left one did. This repetition is the source of f3's exponential running time. Had the code been written as return 2 * f3(n - 1);, the return value would have stayed the same (2n−1), but only one call would be made at each level. The relation would reduce to T(n) = T(n − 1) + c and the time would be Θ(n).

f3(3)= 4f3(2)= 2f3(2)= 2f3(1)= 1f3(1)= 1f3(1)= 1f3(1)= 1
Figure 2.14: The completed call tree of f3(3). Next to each node is the value it returns. The four leaves return 1, the two f3(2) return 2, the root returns 4. The tree has 7 nodes.

2.4.4Unrolling the recurrence

In the unrolling method, the T(n − 1) on the right-hand side of the relation is replaced by its own definition. After a few repetitions a pattern appears in the coefficients. The pattern is written in general form and the step at which the base case is reached is found.

Example 2.4

Solve the relation T(n) = 2T(n − 1) + c, T(1) = c by unrolling.

  1. The relation itself: T(n) = 2T(n − 1) + c. Two subcalls, constant extra work.
  2. Unrolling once: substitute T(n − 1) = 2T(n − 2) + c: T(n) = 2[2T(n − 2) + c] + c = 4T(n − 2) + 3c.
  3. Once more: substitute T(n − 2) = 2T(n − 3) + c: T(n) = 4[2T(n − 3) + c] + 3c = 8T(n − 3) + 7c.
  4. The pattern: the coefficients of T are 2, 4, 8; those of c are 1, 3, 7. The first are powers of two, the second are powers of two minus one. After k steps: T(n) = 2k T(n − k) + (2k − 1)c.
  5. Reaching the base case: when n − k = 1, that is, k = n − 1, use T(1) = c: T(n) = 2n−1c + (2n−1 − 1)c = (2n − 1)c.
  6. Result: T(n) = Θ(2n).

The result agrees exactly with the number of calls of f3: each call does c work and there are 2n − 1 calls. The formula can be checked with small values: T(1) = c, T(2) = 3c, T(3) = 7c. Counted in Java, f3(16) makes 65,535 calls and f3(32) makes 4,294,967,295; both equal 2n − 1. When n goes from 16 to 32, the number of calls grows by a factor of 65,537. This is the signature of exponential growth: when the input doubles, the time reaches a value close to its square.

In unrolling it is also possible to neglect the extra work (c) and write T(n) = 2k T(n − k). This gives T(n) = 2n−1 T(1) and the growth class does not change. The extra work only doubles the constant factor.

4332222111111111 · c2 · c4 · c8 · c
Figure 2.15: The recursion tree of f3(4). The number in each node is its input. The work of the levels is c, 2c, 4c, 8c; the total is 15c = (24 − 1)c.

Unrolling also applies to other subtractive relations. Unrolling T(n) = T(n − 1) + n, T(1) = 1 gives T(n) = n + (n − 1) + … + 2 + 1 = n(n + 1)/2: Θ(n2). This relation arises in algorithms that do n work at each step and shrink the problem by only one. The worst case of quicksort is an example.

Common mistake

Memorizing the rule “two recursive calls mean exponential time.” In f3 two calls give Θ(2n) because the input shrinks by only one and the depth of the tree is n. If the input halved, the depth would be log2 n and the time would drop to linear. What decides is not the number of calls but the joint effect of the number of calls and the way the input shrinks.

2.5The Master Theorem

Unrolling works for every recurrence, but it is laborious. A large share of algorithms use the divide-and-conquer approach, which splits the problem into pieces of equal size. The recurrences of these algorithms always have the same form. The Master Theorem gives a ready-made result for recurrences of this form. The theorem rests on a general method published by Jon Bentley, Dorothea Haken, and James Saxe in 1980; the name “Master Theorem” became popular through the textbook of Cormen and colleagues.

2.5.1The divide-and-conquer recurrence

A divide-and-conquer algorithm splits a problem of size n into a subproblems of size n/b each, solves the subproblems recursively, and combines the results. Its recurrence is:

T(n) = a · T(n/b) + f(n), a ≥ 1, b > 1

  • a: the number of subproblems (recursive calls).
  • b: the shrinking ratio; each subproblem has size n/b.
  • f(n): the work the call itself does, that is, the work of splitting the problem and combining the results.

The recursion tree of this recurrence has a regular structure (Figure 2.16). There is a single node at the root, and it does f(n) work. Each node has a children; level j has aj nodes, each dealing with a problem of size n/bj. Since the input is divided by b at every level, the depth of the tree is logb n. The number of leaves at the last level is

alogb n = nlogb a

The equality of the two expressions is seen by taking logb of both sides: both give logb n · logb a. Since each leaf does constant work, the total work of the leaves is Θ(nlogb a). This quantity is at the center of the theorem: f(n) is always compared with it.

f(n)f(n/b)f(n/b)…f(n/b)a children· ·· ·· ·⋮⋮Θ(1)Θ(1)Θ(1)Θ(1)Θ(1)Θ(1)Θ(1)Θ(1)…f(n)a · f(n/b)a² · f(n/b²)nlog b a · Θ(1)depth: logb n
Figure 2.16: The recursion tree of the recurrence T(n) = aT(n/b) + f(n). There is f(n) work at the root, a total of a · f(n/b) at the first level, and a2 · f(n/b2) at the second. The depth is logb n; at the leaves a total of nlogb a · Θ(1) work is done.

2.5.2The three cases

The theorem compares f(n) with the leaf work nlogb a. The comparison has three outcomes: the work near the root dominates, the work at the leaves dominates, or the levels are balanced. Below is the commonly used form of the theorem, written with the polynomial degree c of f(n).

Theorem 2.1 (Master Theorem)

Let a ≥ 1 and b > 1 be constants and T(n) = aT(n/b) + f(n).

  1. If f(n) = O(nc) for some c < logb a, then T(n) = Θ(nlogb a). (The leaves dominate.)
  2. If f(n) = Θ(nc) for c = logb a, then T(n) = Θ(nlogb a · log n). (The levels are balanced.)
  3. If f(n) = Ω(nc) for some c > logb a, and a constant k < 1 exists such that a · f(n/b) ≤ k · f(n) for every sufficiently large n, then T(n) = Θ(f(n)). (The root dominates.)
Table 2.16: The three cases of the Master Theorem (c: the polynomial degree of f(n)).
CaseConditionResultInterpretation
1f(n) = O(nc), c < logb aΘ(nlogb a)leaves dominate
2f(n) = Θ(nc), c = logb aΘ(nlogb a · log n)levels balanced
3f(n) = Ω(nc), c > logb a and a · f(n/b) ≤ k · f(n), k < 1Θ(f(n))root dominates

The use of different notations in the three cases is no accident. In Case 1 an upper bound on f(n) suffices, because the leaf work is already larger than f and swamps it. In Cases 2 and 3, writing only f(n) = O(nc) is not enough. For example f(n) = 1 is also O(n2); but the solution of T(n) = T(n/2) + 1 cannot be Θ(n2). This is why Case 2 requires f = Θ(nc), and Case 3 requires f = Ω(nc) and in addition the regularity condition. When these conditions hold, the results are given with Θ, that is, as tight bounds.

The regularity condition is specific to Case 3: a · f(n/b) ≤ k · f(n). It means that the total work of the root's children is no more than a constant fraction of the root's own work. Thus the work grows steadily toward the root. For polynomials such as f(n) = nc the condition holds automatically: a(n/b)c = (a/bc) nc, and since c > logb a, a/bc < 1; one can take k = a/bc.

2.5.3Why three cases? Level sums

Why the theorem has three cases becomes clear when we look at the level sums of the recursion tree. Let f(n) = nc. Level j has aj nodes, each doing (n/bj)c work. The total work of the level is

aj · (n/bj)c = nc · (a/bc)j

The level sums form a geometric series with ratio r = a/bc. T(n) is the sum of this series from j = 0 to logb n. The behavior of a geometric series depends only on the ratio:

  • r > 1: the series grows. The last term, that is, the leaves, determines the sum. This is Case 1. Example: for 4T(n/2) + n, r = 4/2 = 2; the level sums grow as n, 2n, 4n, … and the result is Θ(n2).
  • r = 1: the terms are equal. Every level does the same work; the total is the number of levels times the work per level. This is Case 2. Example: for 2T(n/2) + n, r = 2/2 = 1; each of the log n levels does n work and the result is Θ(n log n).
  • r < 1: the series shrinks. The first term, that is, the root, determines the sum. This is Case 3. Example: for 2T(n/2) + n2, r = 2/4 = 1/2; the level sums shrink as n2, n2/2, n2/4, …, their total does not exceed 2n2 and the result is Θ(n2).
4T(n/2) + nj=0j=1j=2j=3r = 2 > 1: grows 2T(n/2) + nj=0j=1j=2j=3r = 1: constant 2T(n/2) + n²j=0j=1j=2j=3r = 1/2 < 1: shrinks
Figure 2.17: The level sums of the three cases; each bar is the total work of one level. Left, 4T(n/2) + n: the bars grow (r = 2), the leaves dominate. Middle, 2T(n/2) + n: the bars are equal (r = 1). Right, 2T(n/2) + n2: the bars shrink (r = 1/2), the root dominates.

The ratio being greater than 1 is the same as c < logb a: r > 1 ⇔ bc < a ⇔ c < logb a. The three cases of the Master Theorem thus correspond to the geometric series growing, staying constant, or shrinking. Instead of memorizing the theorem, it is enough to keep this picture in mind: a is compared with bc.

These results can also be checked with a small computation. When the recurrences are computed directly with T(1) = 1, for n = 16 the recurrence 2T(n/2) + n gives 80, which is the value of n log2 n + n. The recurrence 2T(n/2) + n2 gives 496, that is, 2n2 − n; the n2 = 256 at the root is more than half of the total.

2.5.4Example: 2T(n/2) + n

Example 2.5

Solve the recurrence T(n) = 2T(n/2) + Θ(n) with the Master Theorem.

  1. Reading the parameters. Two subproblems (a = 2), each of half the size (b = 2), linear merging work (f(n) = Θ(n)).
  2. The exponent of the leaf work. logb a = log2 2 = 1; the leaf work is n1 = n.
  3. The degree of f(n). f(n) = Θ(n1), that is, c = 1.
  4. Comparison. c = logb a = 1: the exponents are equal, and each level does the same amount (n) of work. Case 2.
  5. Result. T(n) = Θ(nlogb a · log n) = Θ(n log n).

This recurrence turns up in several of the best-known algorithms.

  • Merge sort: the array is split in two, the two halves are sorted separately, and the sorted halves are merged in Θ(n) time.
  • f5: one of the example functions of this chapter; it calls f1(n) (linear work) and calls itself twice with n/2.
  • Quicksort: if the pivot splits the array into two equal parts every time, the recurrence is the same.

2.5.5More examples

Table 2.17 applies the theorem to frequently encountered recurrences. In each row logb a is computed first, then the degree c of f(n) is compared with it. The logarithm values were computed with Python.

Table 2.17: The Master Theorem applied to example recurrences.
Recurrencea, blogb acCaseResultAlgorithm
T(n/2) + 11, 2002Θ(log n)binary search
2T(n/2) + 12, 2101Θ(n)f4, tree traversal
2T(n/2) + n2, 2112Θ(n log n)f5, merge sort
3T(n/2) + n3, 2≈ 1.58511Θ(n1.585)Karatsuba multiplication
4T(n/2) + n4, 2211Θ(n2)—
7T(n/2) + n27, 2≈ 2.80721Θ(n2.807)Strassen's algorithm
2T(n/2) + n22, 2123Θ(n2)—
T(n/2) + n1, 2013Θ(n)quickselect (average)

The first row of the table is binary search: at each step a single subproblem (a = 1) of half the size is solved and constant work is done. Since log2 1 = 0 and c = 0, Case 2 applies: Θ(n0 · log n) = Θ(log n). It may seem surprising that a constant f(n) falls under Case 2; but the tree has a single node at each level, and each level does the same constant work.

The Karatsuba and Strassen rows show the power of divide and conquer. Multiplying two n-digit numbers by the method taught in school takes Θ(n2). Splitting the numbers in two and making four half-size multiplications does not change this: 4T(n/2) + n = Θ(n2). In 1962 Anatoly Karatsuba showed that one of the four products can be computed from the others. With three multiplications the recurrence becomes 3T(n/2) + n and the result drops to Θ(nlog2 3) ≈ Θ(n1.585). In 1969 Volker Strassen applied the same idea to matrix multiplication: seven subproducts instead of eight. The recurrence 8T(n/2) + n2 gives Θ(n3); 7T(n/2) + n2 gives Θ(nlog2 7) ≈ Θ(n2.807). In both examples removing a single subcall lowered the exponent. Because in Case 1 only a and b determine the result, every reduction in a turns directly into a gain.

In the Case 3 rows the regularity condition must also be checked. For 2T(n/2) + n2, 2 · (n/2)2 = n2/2 ≤ ½ · n2, so the condition holds with k = ½. For T(n/2) + n, 1 · (n/2) ≤ ½ · n, again with k = ½.

Example 2.6

Solve three recurrences: (a) T(n) = 3T(n/3) + n, (b) T(n) = 9T(n/3) + n, (c) T(n) = T(n/2) + n.

  1. (a) a = 3, b = 3, log3 3 = 1; f(n) = n, c = 1. The exponents are equal: Case 2, T(n) = Θ(n log n). In the tree each level splits into three parts but the total work is still n; the number of levels is log3 n. For n = 729 direct computation gives 5103 = 729 · 6 + 729.
  2. (b) a = 9, b = 3, log3 9 = 2; c = 1 < 2. Case 1, T(n) = Θ(n2). The work of each level is three times that of the previous one (r = 9/3 = 3); the leaves dominate.
  3. (c) a = 1, b = 2, log2 1 = 0; c = 1 > 0. Regularity: 1 · (n/2) ≤ ½ · n, k = ½ < 1. Case 3, T(n) = Θ(n). The total is n + n/2 + n/4 + … < 2n.

2.5.6Recurrences the theorem does not cover

The Master Theorem is powerful, but it applies only to recurrences of a particular form. For recurrences outside this form another method is needed.

  • Subtractive recurrences. T(n) = 2T(n − 1) + c (f3) or T(n) = T(n − 1) + n: the subproblem is n − 1, not n/b. Unrolling is used.
  • A non-polynomial gap. T(n) = 2T(n/2) + n / log n: nlog2 2 = n is compared with f(n) = n / log n. f(n) is smaller than n, but only by a log factor, not by a polynomial factor like nε. So neither the condition of Case 1 nor that of Case 2 holds. (The solution of this recurrence is Θ(n log log n) and is found with a recursion tree.)
  • Unequal splits. T(n) = T(n/3) + T(2n/3) + n: the subproblems have different sizes. In the recursion tree the work at each level is at most n and the longest branch has depth log3/2 n; the result is Θ(n log n). Recurrences of this kind are generally solved by the Akra–Bazzi method.
  • Non-constant a or a < 1. T(n) = 2n T(n/2) + n or T(n) = ½ T(n/2) + n: the theorem's assumption that a ≥ 1 is constant is violated.

A commonly used extension of the basic form carries Case 2 over to logarithmic factors: if f(n) = Θ(nlogb a · logk n) and k ≥ 0, then T(n) = Θ(nlogb a · logk+1 n). For example, for T(n) = 2T(n/2) + n log n, k = 1 and the result is Θ(n log2 n). This extension also solves some recurrences that the basic form calls “not applicable.”

Common mistake

In Case 3, checking only the condition c > logb a and forgetting regularity. For polynomials the condition holds automatically, so the mistake usually does not change the result; but in examples where f(n) oscillates the condition fails. In the recurrence T(n) = T(n/2) + n(2 − cos n), c = 1 > 0; but for the values of n where cos n is near 1 and cos(n/2) near −1, the ratio f(n/2)/f(n) approaches 1.5 and no k < 1 satisfies the condition. When using Case 3, the inequality a · f(n/b) ≤ k · f(n) should be written out explicitly.

2.6Application: f4 and f5

This section solves two recursive functions with all three methods: tracing, the recursion tree, and the Master Theorem. f4 differs from f3 only in the argument of the recursive calls (n / 2 instead of n - 1); but this change brings the time down from exponential to linear. f5 adds linear work to f4 at each call and gives the recurrence of merge sort.

2.6.1f4: two calls, n/2

public int f4(int n) {
  if (n <= 1) {
    return 1;
  }
  return f4(n / 2) + f4(n / 2);
}
  • Base case: returns 1 when n ≤ 1; O(1).
  • Recursive case: when n > 1, f4(n / 2) is called twice and the results are added. The addition is constant work.

T(n) = 2T(n/2) + O(1), T(1) = O(1)

In Java n / 2 is integer division; the fractional part is discarded. In the analysis n is assumed to be a power of two, so that every division is exact. This assumption does not change the growth class.

The only difference from f3 is that the input is n/2 instead of n − 1. The number of calls still doubles at every level; but since the input halves at every level, the tree is only log2 n levels deep. For n = 8 the levels have 1, 2, 4, 8 calls and the inputs are 8, 4, 2, 1. In f3 a tree starting from 8 would descend 8 levels; here it ends at 4 levels.

n = 81 calln = 42 callsn = 24 callsn = 18 callsinput halves: only log₂ 8 + 1 = 4 levels, 1 + 2 + 4 + 8 = 15 = 2n − 1 calls
Figure 2.18: The levels of f4(8). The input halves at each level (8, 4, 2, 1) and the number of calls doubles (1, 2, 4, 8). There are only log2 8 + 1 = 4 levels; in all 1 + 2 + 4 + 8 = 15 = 2n − 1 calls are made.

Two calls do not always mean exponential time. What decides is how much the input shrinks. If the input decreases by one, the tree descends to depth n and reaches 2n leaves. If the input halves, the tree stays at depth log2 n and reaches 2log2 n = n leaves.

2.6.2The recursion tree of f4

In the recursion-tree method each call is drawn as a node and the work it does is written next to it. Then the work of each level is added up, and finally the level sums are added. For f4(8):

  1. Root: f4(8) does only constant work (c) and starts two calls. The work of level 0 is c.
  2. Level 1: two calls f4(4); total 2c.
  3. Level 2: four calls f4(2); total 4c. The work per level doubles at each step.
  4. Leaves: eight f4(1); total 8c = n · c.

The total is c(1 + 2 + 4 + 8) = 15c = (2n − 1)c; that is, Θ(n). The level sums grow geometrically and the last term, the work of the leaves, determines the sum. Counted in Java, f4(16) makes 31 calls and f4(32) makes 63; both equal 2n − 1. The return value of the function also equals the number of leaves: f4(n) = n.

8442222111111111 · c2 · c4 · c8 · c
Figure 2.19: The recursion tree of f4(8). The number in each node is its input. The column on the right gives the level sums: c, 2c, 4c, 8c. The eight leaves, drawn in orange, do more than half of the total work.

If n is not a power of two, integer division comes into play. f4(10) first calls two f4(5), each f4(5) calls two f4(2), and each f4(2) calls two f4(1). The number of calls is 15 and the return value is 8. The result is as if it had worked for the largest power of two (8) not exceeding n; the growth class is still linear.

2.6.3Solving f4 with the Master Theorem

Example 2.7
  1. Matching. The recurrence T(n) = 2T(n/2) + O(1) is compared with the general form: a = 2, b = 2, f(n) = O(1).
  2. Leaf work. logb a = log2 2 = 1; the leaf work is n1 = n.
  3. Comparison. f(n) = O(1) = O(n0), that is, c = 0. 0 < 1: Case 1.
  4. Result. T(n) = Θ(nlog2 2) = Θ(n).

The Master Theorem gives the result of the recursion tree without computing the sum. In the tree we counted 2n − 1 nodes; the theorem merely says “the leaves dominate,” and since the number of leaves is n, it arrives at Θ(n).

The memory of f4 is a different question. Because the calls run in sequence, the stack holds only one branch at a time: f4(n), f4(n/2), …, f4(1). The length of this branch is log2 n + 1; while f4(16) runs, the stack holds at most 5 frames. The time is Θ(n) and the auxiliary space is Θ(log n).

Common mistake

Saying of f4, “the input halves at every step, so it is O(log n).” This reasoning is correct for binary search, which makes a single call. f4 makes two calls, and both branches descend all the way. log n is only the stack depth, that is, it gives the memory; the time is Θ(n).

2.6.4f5: linear work and two calls

public int f5(int n) {
  if (n <= 1) {
    return 1;
  }
  return f1(n) + f5(n / 2) + f5(n / 2);
}
  • Base case: returns 1 when n ≤ 1; O(1).
  • Recursive case: when n > 1, f1(n) is called first. f1 is a loop that runs n rounds and does Θ(n) work. Then f5(n / 2) is called twice.

T(n) = 2T(n/2) + f1(n) = 2T(n/2) + Θ(n)

Its only difference from f4 is the linear work done at each call. The recurrence is the same as that of merge sort. A common mistake here is to consider the two parts separately and add them: “f1 is linear, the recursion is logarithmic, the total is O(n + log n) = O(n).” This is wrong. f1 is called not only at the root but at every node of the tree; each node does as much work as its input size. The sum of these works must be found.

2.6.5Code trace: f5(4)

Table 2.18: Trace of f5(4) (from the output of a copy run in Java).
StepEventValue
1f5(4) is called; 4 > 1—
2f1(4): a loop of 4 rounds, 4 units of work4
3the left f5(2) is called; f1(2): 2 units of work2
4two f5(1): base case1, 1
5f5(2) = f1(2) + f5(1) + f5(1) = 2 + 1 + 14
6the right f5(2): the same work is done again from scratch4
7f5(4) = f1(4) + f5(2) + f5(2) = 4 + 4 + 412

The result is 12. This number also shows how the work is distributed over the levels. At the root f1(4) does 4 units, and at the first level the two f1(2) do 4 units in all. Each of the four leaves returns 1; total 4. The work of each level is n = 4. There are log2 4 = 2 inner levels and one leaf level: 2 · 4 + 4 = 12 = n log2 n + n.

f5(4)f1: 4 = 12f5(2)f1: 2 = 4f5(2)f1: 2 = 4f5(1)= 1f5(1)= 1f5(1)= 1f5(1)= 142 + 21 + 1 + 1 + 1level work
Figure 2.20: The completed tree of f5(4). Below each node is written the work done by f1 and the total the node returns: at the root f1 does 4 work and f5(4) returns 12; at the f5(2) nodes f1 does 2 work and each returns 4. The column on the right gives the level work: 4, 2 + 2, 1 + 1 + 1 + 1.

2.6.6The recursion tree of f5 and the Master Theorem

In the tree of f5(8) the pattern is easier to see (Figure 2.21).

  1. Root: inside f5(8), f1(8) takes 8 steps.
  2. Level 1: two f5(4), each with 4 steps by f1(4); total 8.
  3. Level 2: four f5(2), each with 2 steps; total again 8.
  4. Leaves: eight f5(1), each 1; total 8.

The total is 3 · 8 + 8 = 32 = n log2 n + n, and in Java f5(8) really returns 32. Each level does n work and there are log2 n inner levels; the result is Θ(n log n). The formula holds on larger inputs too: f5(16) = 80 = 16 · 4 + 16, f5(32) = 192 = 32 · 5 + 32.

84422221111111184 + 4 = 84 · 2 = 88 · 1 = 8
Figure 2.21: The recursion tree of f5(8). It has the same shape as the tree of f4, but each node does as much work as its input size. The level sums are equal: 8 = 4 + 4 = 4 · 2 = 8 · 1.

The solution with the Master Theorem follows the same steps as for f4; only f(n) has changed:

  1. T(n) = 2T(n/2) + Θ(n): a = 2, b = 2, f(n) = Θ(n).
  2. logb a = 1, c = 1. Exponents equal: Case 2.
  3. T(n) = Θ(nlogb a · log n) = Θ(n log n).
Table 2.19: Comparison of f4 and f5.
f4f5
Calls2 × n/22 × n/2
Extra work f(n)O(1)Θ(n)
c versus logb a0 < 11 = 1
Case12
Level sumsc, 2c, 4c, … (growing)n, n, n, … (equal)
ResultΘ(n)Θ(n log n)

The table sums up what the f3–f4–f5 triple teaches. All three functions call themselves twice. The difference between f3 and f4 is the way the input shrinks (n − 1 versus n/2), and it brings the result down from Θ(2n) to Θ(n). The difference between f4 and f5 is the extra work (constant versus linear), and it raises the result from Θ(n) to Θ(n log n).

2.7Comparison and amortized analysis

2.7.1f1–f6: measured step counts

The classes of the six functions found by analysis can be checked by running the functions. Table 2.20 gives the measured step count of each function for n = 16 and n = 32. For f1, f2, f5, and f6 the return value is used, and for f3 and f4 the call count. The values were measured in Java.

Table 2.20: Measured step counts of f1–f6. The ratio column gives how the step count changes when n doubles (the counter is long; f3(32) ≈ 4.3·109 calls).
FunctionRecurrence / sumn = 16n = 32RatioClass
f1 (return)Σ 1 = n1632× 2Θ(n)
f2 (return)Σ i21,24010,416× 8.4Θ(n3)
f3 (calls)2T(n − 1) + c65,5354,294,967,295× 65,537Θ(2n)
f4 (calls)2T(n/2) + c3163× 2Θ(n)
f5 (return)2T(n/2) + n80192× 2.4Θ(n log n)
f6 (return)i ← 2i45+ 1Θ(log* n) (mathematical model; in Java, n ≤ 65536)

The ratio column is a practical test that gives away the growth class. When n doubles, linear functions (f1, f4) double. The linearithmic f5 grows by a factor slightly above 2, 2.4; the excess comes from the factor log n rising from 4 to 5. The cubic f2 grows by about a factor of 8. The ratio of the exponential f3 is 216 + 1 = 65,537; when the input doubles, the step count roughly squares. f6 increases by just one step.

This test is an experimental way of verifying an analysis, and it is also used when the complexity of a piece of code is unknown. A program is run with different values of n, the time or step count is measured, and the ratio of consecutive measurements is examined. Sedgewick and Wayne call this method the “doubling experiment.” The interactive step counter in the slides performs the same experiment for every n from 1 to 40 and shows the results as bars on a logarithmic scale. There, the number of calls is also counted for f5, so the values are slightly larger than those in the table; the ratios, however, show the same class.

2.7.2Amortized analysis

In some data structures most operations are cheap and an occasional few are expensive. In such a structure, looking at the worst case of a single operation overstates the total cost. Amortized analysis looks at the whole sequence of operations.

Definition 2.7

Amortized analysis finds the cost per operation by dividing the worst-case total cost of a sequence of operations by the number of operations. The value found is called the amortized cost.

The classic example is the dynamic array, such as Java's ArrayList. When the array is full, its capacity is doubled: a new array of twice the size is allocated and all the elements are copied into it. This insertion is expensive. Insertions made while there is room are a single write and cost 1 unit. The code below spells out this logic; the cost is the sum of the number of writes and the number of elements copied.

int[] data = new int[1];
int size = 0;
long cost = 0;

void add(int x) {
  if (size == data.length) {                // array is full
    int[] bigger = new int[2 * data.length]; // double the capacity
    for (int i = 0; i < size; i++) {
      bigger[i] = data[i];                  // copy: 1 unit
      cost++;
    }
    data = bigger;
  }
  data[size++] = x;                         // write: 1 unit
  cost++;
}
Example 2.8

Nine elements are added to an empty dynamic array of capacity 1. The cost of each insertion (1 write + the number of copies) is:

  1. Insertion 1: there is room, 1 write. Cost 1.
  2. Insertion 2: the array is full; capacity 1 → 2, 1 copy + 1 write. Cost 2.
  3. Insertion 3: full; capacity 2 → 4, 2 copies + 1 write. Cost 3.
  4. Insertion 4: there is room. Cost 1.
  5. Insertion 5: full; capacity 4 → 8, 4 copies + 1 write. Cost 5.
  6. Insertions 6, 7, and 8: there is room. Each costs 1.
  7. Insertion 9: full; capacity 8 → 16, 8 copies + 1 write. Cost 9.

The total is 1 + 2 + 3 + 1 + 5 + 1 + 1 + 1 + 9 = 24 units; the average per insertion is 24/9 ≈ 2.67. The worst cost of a single insertion is 9, but for the whole array 24 < 3 · 9 = 27 units were spent.

112233145516171899total = 24 · average = 2.67
Figure 2.22: Nine insertions into a dynamic array whose capacity starts at 1 and doubles. The orange bars are insertions that include a capacity increase (copying): insertions 2, 3, 5, and 9. Total 24, average 2.67.
Theorem 2.2 (Amortized cost of doubling)

The total cost of n insertions into a dynamic array whose capacity starts at 1 and is doubled when full is less than 3n. The amortized cost per insertion is Θ(1).

Capacity increases occur when the array is full with 1, 2, 4, …, 2k elements, where 2k is the largest power of two smaller than n. The total number of copies is a geometric series: 1 + 2 + 4 + … + 2k = 2k+1 − 1 < 2n. Each insertion also makes one write; that is n units. The total is < 2n + n = 3n. Divided by n, the cost per insertion comes out below 3, that is, constant. □

The theorem rests on the moments when copying is expensive being rare. A capacity increase copies m elements, but after it m more insertions are done cheaply. The cost of the expensive operation is “spread” over the cheap operations that follow it. In a count done with Python, the total cost of 1000 insertions comes out to 2023; this is below 3n = 3000.

Why doubling matters becomes clear when it is compared with growing by a fixed amount. If the capacity were increased by just 1 when the array is full, every insertion would copy the whole array. The total cost of n insertions would be 1 + 2 + … + n = n(n + 1)/2, that is, Θ(n2); for n = 1000, 500,500 units. Even if the capacity were increased by a fixed k, the result would not change; only the constant factor would shrink.

Amortized analysis differs from average-case analysis. The average case rests on a probability distribution over the inputs and gives the “expected” time. In amortized analysis there is no probability: a guarantee is given for every sequence of operations, even the worst one. In a dynamic array a single insertion can take Θ(n); but whatever the order of insertions, the total of n insertions does not exceed 3n. There are three standard methods of finding the amortized cost: the aggregate method (used here), the accounting method, and the potential method.

Common mistake

Reading amortized Θ(1) as “every insertion takes constant time.” The amortized bound says nothing about the time of a single operation; the 9th insertion took 9 units. In real-time systems where every operation must be short, an amortized bound is not enough; a worst-case bound is needed.

2.8Common mistakes

The most important of the mistakes given in the boxes throughout the chapter are collected here:

  • Equating Big O with the worst case. O is an upper bound, while the worst case is a kind of input. “The best case is O(1)” is a valid sentence.
  • Writing constants and small terms. One does not write O(3n + 3) or O(n2/3 + n); O(n) and O(n2) suffice.
  • The rule “nested loops = n2.” The bound of the inner loop determines the result. In f2 the bound is i2, so the result is Θ(n3); a loop advancing with i *= 2 runs log n rounds.
  • The rule “two calls = exponential.” f3 (n − 1) is Θ(2n), f4 (n/2) is Θ(n). The way the input shrinks determines the result.
  • Applying the Master Theorem to every recurrence. The theorem does not hold for recurrences that contain T(n − 1), split unevenly, or have a non-polynomial gap such as f(n) = n / log n.
  • Forgetting regularity in Case 3. c > logb a is not enough; a · f(n/b) ≤ k · f(n), k < 1 must hold as well.
  • Confusing the memory of recursion with the call count. Memory is determined by the number of frames open at the same time, that is, the depth: Θ(n) for f3, Θ(log n) for f4.
  • Confusing a shift with a multiplication. i = 1 << i is 2i, not 2 * i. The tight bound for f6 is Θ(log* n).

2.9Summary

  • Time complexity T(n) gives how the number of basic operations grows with the input size n. Space complexity S(n) gives the memory used in addition to the input; in recursion the depth of the call stack counts toward this memory.
  • Timing depends on the machine and gives no prediction for large inputs. In the RAM model every basic operation counts as one unit; linear search takes 3n + 3 steps in the worst case and is Θ(n).
  • The best, worst, and average case concern different inputs of the same size. In linear search they make 1, n, and (n + 1)/2 comparisons respectively.
  • f = O(g) is an upper bound, f = Ω(g) a lower bound, and f = Θ(g) a tight bound. Bounds are proved by finding the constants c and n0; for 3n2 + 5n + 2, c1 = 3, c2 = 4, n0 = 6. The case (which input) and the bound (O, Ω, Θ) are separate notions.
  • Rules of calculation: constant factors and lower-order terms are dropped; for sequential code the larger remains, for nested code the round counts are multiplied or added; the base of a logarithm is irrelevant, while the base of an exponential matters. The order of growth: 1 < log n < √n < n < n log n < n2 < n3 < 2n < n!.
  • In loop analysis the inner round count is written for each outer round and added up. f1: Σ 1 = n, Θ(n). f2: Σ i2 = (n − 1)n(2n − 1)/6, Θ(n3). A multiplicative loop is Θ(log n); a multiplicative loop with j < i inside it is Θ(n) because of the geometric series.
  • In f6, i = 1 << i, that is, i ← 2i; the round count is log* n + 1. O(log n) is correct but not tight; the tight bound is Θ(log* n). In Java, for n > 65,536 the shift overflows and the loop does not terminate.
  • A recurrence relation is built from the number of calls, the way the input shrinks, and the extra work. f3: T(n) = 2T(n − 1) + c; by unrolling, (2n − 1)c = Θ(2n). Its memory is only Θ(n).
  • The Master Theorem compares f(n) in T(n) = aT(n/b) + f(n) with the leaf work nlogb a: leaves dominate (Case 1), levels balanced (Case 2, an extra factor log n), root dominates (Case 3, with the regularity condition). The three cases correspond to the geometric series with ratio a/bc growing, staying constant, or shrinking.
  • The theorem does not apply to subtractive recurrences, recurrences with unequal splits, a non-polynomial gap in f(n), or a non-constant a.
  • f4: 2T(n/2) + 1, Case 1, Θ(n); 2n − 1 calls, Θ(log n) memory. f5: 2T(n/2) + n, Case 2, Θ(n log n); f5(n) = n log2 n + n.
  • Amortized analysis divides the total cost of a sequence of operations by the number of operations. In a dynamic array that doubles, the total of n insertions is less than 3n; insertion is amortized Θ(1). Unlike the average case, it uses no probability.
Table 2.21: Summary of the six example functions.
FunctionStructureAnalysisTimeAuxiliary space
f1single loopΣ 1 = nΘ(n)Θ(1)
f2inner loop j < i * iΣ i2Θ(n3)Θ(1)
f3two calls, n − 12T(n − 1) + c, unrollingΘ(2n)Θ(n)
f4two calls, n/22T(n/2) + 1, Case 1Θ(n)Θ(log n)
f5f1(n) + two calls, n/22T(n/2) + n, Case 2Θ(n log n)Θ(log n)
f6i = 1 << ii ← 2iΘ(log* n) (mathematical model; in Java, n ≤ 65536)Θ(1)

2.10Key terms

These are the terms introduced in this chapter.

  • time complexity
  • space complexity
  • complexity class
  • growth rate
  • random-access machine (RAM model)
  • best case
  • worst case
  • average case
  • asymptotic notation
  • Big O notation
  • Big Omega (Ω)
  • Big Theta (Θ)
  • upper bound
  • lower bound
  • tight bound
  • constant time
  • logarithmic
  • linear
  • linearithmic
  • quadratic
  • cubic
  • exponential
  • factorial
  • polynomial time
  • iterated logarithm
  • recursion
  • base case
  • call stack
  • recurrence relation
  • recursion tree
  • divide and conquer
  • Master Theorem
  • regularity condition
  • amortized analysis
  • dynamic array

2.11Test Yourself

  1. For the bound 5n3 + 2n + 8 = O(n3), c = 6 is chosen. What is the smallest n0 for which the inequality 5n3 + 2n + 8 ≤ 6n3 holds for every n ≥ n0?

    Answer

    5n3 + 2n + 8 ≤ 6n3 ⇔ n3 ≥ 2n + 8. At n = 2, 8 < 12 and the inequality fails; at n = 3, 27 ≥ 14 and it holds. As n increases, n3 grows faster than 2n + 8, so the inequality always holds from there on: n0 = 3. Check: at n = 3, 149 ≤ 162.

  2. How many times does the fragment for (i = 0; i < n; i++) for (j = i; j < n; j++) x++; execute x++ for n = 6? What is the growth class?

    Answer

    In round i the inner loop runs n − i times: 6 + 5 + 4 + 3 + 2 + 1 = 21. In general n(n + 1)/2, that is, Θ(n2). That the inner loop depends on the outer counter halves the total but does not change the class.

  3. For n = 64, how many rounds does the loop for (int i = 1; i * i <= n; i++) x++; run? What is the growth class?

    Answer

    The loop continues while i2 ≤ n, that is, i ≤ √n. For n = 64, i = 1, …, 8: 8 rounds. The class is Θ(√n); primality testing by trial division uses this pattern.

  4. Which of the statements 2n+1 = O(2n) and 22n = O(2n) is true?

    Answer

    The first is true: 2n+1 = 2 · 2n; c = 2, n0 = 1 suffice. The second is false: 22n = 4n and the ratio 4n/2n = 2n goes to infinity; no constant c can close this gap. A constant added to the exponent only brings a constant factor; a constant multiplying the exponent changes the base.

  5. What is the solution of the recurrence T(n) = 2T(n/4) + √n by the Master Theorem?

    Answer

    a = 2, b = 4, log4 2 = 1/2. f(n) = √n = n1/2, c = 1/2. Exponents equal: Case 2, T(n) = Θ(√n log n). Check: with T(1) = 1, T(256) = 80 = 16 · 4 + 16.

  6. What is the solution of the recurrence T(n) = 5T(n/2) + n2? Do the level sums grow or shrink?

    Answer

    log2 5 ≈ 2.32 > c = 2: Case 1, T(n) = Θ(nlog2 5) ≈ Θ(n2.32). The ratio is r = 5/22 = 1.25 > 1; the level sums grow by a factor of 1.25 at each level, and the leaves dominate.

  7. What is the closed form of the recurrence T(n) = T(n − 1) + 1, T(1) = 1, found by unrolling? Why does the Master Theorem not apply?

    Answer

    T(n) = T(n − 1) + 1 = T(n − 2) + 2 = … = T(n − k) + k. At k = n − 1, T(n) = T(1) + n − 1 = n: Θ(n). Because the subproblem is n − 1, not n/b, the recurrence does not fit the form of the Master Theorem. If the input of a recursion with a single call decreases by one at each step, the time is n times the work of each call.

  8. How many calls does f4(10) make and what does it return? (In Java n / 2 is integer division.)

    Answer

    f4(10) calls two f4(5), each f4(5) calls two f4(2), each f4(2) calls two f4(1). The calls number 1 + 2 + 4 + 8 = 15. Eight leaves return 1; the result is 8. The tree has the same shape as the tree for input 8.

  9. Seventeen elements are added to an empty dynamic array of capacity 1 that doubles when full. How many copies are made in all, what is the total cost, and what is the final capacity?

    Answer

    Capacity increases occur at insertions 2, 3, 5, 9, and 17; the copies are 1 + 2 + 4 + 8 + 16 = 31. With 17 writes the total is 48 units, which stays below 3 · 17 = 51. The final capacity is 32.

  10. What are the number of x++ executions and the growth class of the fragment for (i = 0; i < n; i++) for (j = 1; j < n; j *= 2) x++; for n = 10?

    Answer

    The inner loop is independent of the outer counter; it runs 4 rounds, at j = 1, 2, 4, 8. The outer loop runs 10 rounds; total 10 · 4 = 40. In general n · ⌈log2 n⌉, that is, Θ(n log n).

2.12Further reading

  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (4th ed., 2022), Chapters 3 and 4: give the formal definitions of asymptotic notation, the substitution and recursion-tree methods, and the proof of the Master Theorem; they also touch on the Akra–Bazzi method.
  • R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Section 1.4: combines measuring running time by experiments, the doubling experiment, and mathematical models, with Java examples.
  • J. Kleinberg and É. Tardos, Algorithm Design (2005), Chapters 2 and 5: discuss the notion of efficiency and the polynomial-time criterion; solve divide-and-conquer recurrences clearly with recursion trees.
  • D. E. Knuth, “Big Omicron and Big Omega and Big Theta” (1976): a short article on the history of the O, Ω, and Θ notations and why their present definitions were chosen.

2.13References

  1. J. L. Bentley, D. Haken, J. B. Saxe, “A General Method for Solving Divide-and-Conquer Recurrences”, SIGACT News 12(3), 1980.
  2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022.
  3. J. Kleinberg, É. Tardos, Algorithm Design, Pearson, 2005.
  4. D. E. Knuth, “Big Omicron and Big Omega and Big Theta”, SIGACT News 8(2), 1976.
  5. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.

Related pages: Chapter 2 slides · Slides PDF · © Sercan Külcü. All rights reserved.