Chapter 2: Algorithm Analysis

2.1Algorithms and measurement

Every topic in this course raises the same question: how long does this operation take? Searching an array, inserting into a list, deleting from a tree — each data structure makes some operations fast and others slow, and to say which structure suits which job we must give “fast” and “slow” a precise meaning. That is the job of algorithm analysis. We begin with the notion of an algorithm and two ways to measure its cost: timing it and counting its operations.

2.1.1What is an algorithm?

A recipe takes ingredients (the input), works through a sequence of steps, and produces a dish (the output). Its steps are explicit — “boil the water,” “add the rice,” “simmer for fifteen minutes” — so anyone who follows them gets the same dish, and it ends; nobody stirs forever. An algorithm has the same shape: a step-by-step method that takes an input, carries out its steps, and produces an output.

What happens inside the box in Figure 2.1 — which numbers are compared and swapped, in what order — differs from algorithm to algorithm; many routes lead from the same input to the same output.

That is where analysis begins: of several algorithms for a problem, some need far less time and memory. On small inputs the difference may go unnoticed, but as the input grows one algorithm may finish in a second while another runs for days; Table 2.7 puts numbers on this gap.

Algorithms are grouped by the kind of problem they solve. Table 2.1 lists three groups that recur throughout the course.

Two searching algorithms, linear and binary search, are studied in detail below (2.3.5–2.3.7). Both answer “Is the target in the array, and at which index?”, but one looks at every element and the other at only a few — one of the clearest demonstrations of why the choice of algorithm matters.

2.1.2What makes an algorithm good

A good algorithm solves its problem effectively, and “effectively” breaks down into four criteria — two about cost, two about reliability:

• Time complexity: how the running time, or the number of operations, grows with the input.
• Space complexity: how the memory used grows with the input size (2.4.1).
• Correctness: the right result for every valid input. A wrong answer is useless, however fast (2.4.2).
• Robustness: coping with unexpected inputs and situations without crashing or silently returning a wrong result (2.4.4).

The criteria are not equal. Correctness is non-negotiable: a fast algorithm with wrong answers is always worse than a slow one with right answers. Time and space decide only among correct algorithms. They sometimes conflict — some algorithms buy speed with memory — but not always: in the prefix averages example (2.3.12) the fast solution uses the same memory and simply skips needless work.

Most of this chapter is about time, which most often decides the choice of a data structure. Memory is analyzed with the same notation and methods.

2.1.3Empirical analysis: System.nanoTime()

The most natural way to learn how long a program takes is to run it and time it — empirical analysis. In Java, System.nanoTime() returns a number, and the difference between two calls is the elapsed time in nanoseconds (ns, billionths of a second).

The code below times hasDuplicates, which checks an array for repeated elements, at several sizes. It compares every pair of elements (code and analysis in 2.3.3); for now we only need to know that on an array without duplicates it examines every pair before returning false.

for (int n = 1000; n <= 64000; n *= 2) {
  int[] a = new int[n];
  for (int i = 0; i < n; i++) a[i] = i; // no duplicates
  long start = System.nanoTime();
  hasDuplicates(a);                    // the work being timed
  long elapsed = System.nanoTime() - start;  // ns
  System.out.println(n + " " + elapsed / 1e6 + " ms");
}

• The outer loop doubles n from 1000 — 1000, 2000, 4000, …, 64000 — so seven sizes are tried.
• new int[n] creates an array of n cells, and a[i] = i fills it with 0, 1, 2, …; all values differ, so there are no duplicates.
• start = System.nanoTime() records the moment just before the call hasDuplicates(a).
• System.nanoTime() - start is the elapsed time in nanoseconds; dividing by 10⁶ gives milliseconds (ms), printed next to n.

The value of System.nanoTime() means nothing on its own; it is not the time of day, and only the difference between two readings matters. The time of day — a clock saying “it’s 2:05” — comes from System.currentTimeMillis(). For short intervals nanoTime() is better: its resolution is finer, and it does not jump when the system clock is adjusted.

Good measurements follow three principles:

1. Measure. Read System.nanoTime() immediately before and after the work. Creating and filling the array stay outside; only the call to hasDuplicates is timed.
2. Repeat. One measurement is unreliable. The Java Virtual Machine (JVM) interprets code at first and later compiles frequently run parts to machine code; this just-in-time (JIT) compilation slows the first measurements, and the garbage collector and other programs add noise. So we repeat each measurement and take the median — the middle value of the sorted measurements, which no single outlier can distort.
3. Plot. Plot time against n. What matters is not the times themselves but how much the time grows when n doubles — the subject of the next subsection.

Table 2.2 shows one run of this code on a laptop. The numbers vary between machines and even between runs; we use them only to show how a measurement is read.

The first two rows look odd: 1000 elements took about nine times longer than 2000. The culprit is the JIT, not the algorithm — on the first call hasDuplicates is still interpreted, by the second it is compiled. The first row is a “warm-up” and is ignored. After that the ratio ranges from 3.1 to 5.0, mostly near 4. The 5.0 in the last row is noise: the large array no longer fits in the processor cache, or another program happened to run. Repeating and taking the median removes most such deviations.

2.1.4The doubling experiment

Raw times say little: “727 ms for 64,000 elements” means nothing on another computer. What lasts is how the time grows with the input, and the practical way to find it is the doubling experiment: double the input size at each step and look at the ratio of consecutive times.

Suppose the running time is roughly T(n) ≈ c · n^k, where the constant c depends on the machine and the exponent k on the algorithm. Doubling the input gives

T(2n) / T(n) ≈ c · (2n)^k / (c · n^k) = 2^k

The constant c cancels, so the ratio is machine-independent: a faster computer shrinks c but not the ratio. A ratio of 2 means k = 1, linear growth; 4 means k = 2, quadratic; 8 means k = 3, cubic.

Figure 2.2 shows the expected ratios for four growth rates. (The O(…) notation is defined in 2.2.1; read it for now as “grows roughly like.”) The interesting bar is n log n: the logarithm grows a little when n doubles, so the ratio is slightly above 2:

(2000 · log₂ 2000) / (1000 · log₂ 1000) = 2 · 10.966 / 9.966 ≈ 2.2

This is also why a doubling experiment struggles to tell n from n log n: noise easily blurs 2.0 and 2.2.

2.1.5Limits of empirical analysis

Empirical analysis is concrete — it shows a real program on a real machine — but it has three serious limitations (Goodrich et al., Section 4.1):

• Results depend on the environment: the processor, the memory, the JVM version, whatever else is running. Two algorithms must be timed on the same machine under the same conditions; comparing our timing with one from someone else’s machine is meaningless.
• It covers only the inputs tried. An important kind of input that slows the algorithm down may never be tested. Someone who times hasDuplicates only on arrays of zeros never sees its worst case.
• The algorithm must be fully implemented before anything can be measured, yet decisions are usually needed before the code exists. Implementing and timing ten methods just to pick one is expensive.

The way past these limits is to count an algorithm’s steps instead of timing them. Counting is hardware-independent, holds for every input, and needs no running code — pseudocode will do. Empirical analysis does not replace it but is a good check on it; in Example 2.1 measuring and counting agreed.

2.1.6Counting primitive operations: arrayMax()

First we must decide what to count. A line of Java may become several machine instructions whose timings vary between processors. To avoid such details we assume that certain basic operations each take constant time, and count only how often they run.

If each primitive operation takes at most some constant time, the running time is at most that constant times the operation count. The constant changes from machine to machine; the count does not — a machine-independent measure.

Our first example, arrayMax, finds the largest element of an array:

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

It takes the first element as a provisional maximum, scans the rest of the array, and updates currentMax whenever an element beats it. When the loop ends, currentMax is the largest element of the whole array.

Now count how often each statement runs, for an array of length n, numbering lines from the method header as line 1.

• The assignment before the loop (currentMax = a[0]) and the initialization i = 1 run once each.
• The body runs for i = 1, 2, …, n − 1 — n − 1 iterations — so the comparison and i++ run n − 1 times each.
• The condition i < a.length is tested once more than the body runs: n − 1 times true, then once false at i = n, ending the loop — n tests.
• The update currentMax = a[i] runs only when the comparison is true, so its count depends on the data: anywhere from never to n − 1 times.

Writing u for the number of updates, the total is

1 + 1 + n + (n − 1) + u + (n − 1) + 1 = 3n + 1 + u,   0 ≤ u ≤ n − 1

In the best case, a[0] is the largest and nothing is updated: u = 0, total 3n + 1. In the worst case the array is increasing, every element beats all earlier ones, and every iteration updates: u = n − 1, total 3n + 1 + n − 1 = 4n.

The conclusion matters more than the numbers. Either way the count grows in proportion to n: double n and it roughly doubles. The factors 3 and 4 and the +1 are details that vary between machines anyway, so we drop them and say that arrayMax runs in Θ(n) time in both cases. Θ is defined precisely in 2.2.2.

Which operations count separately is a convention. currentMax = a[i] really reads a cell and assigns a value; counting it as two operations turns 3n + 1 into another linear expression, but the growth stays linear. Changing the counting rules changes only constants — one more reason to drop them.

2.1.7Code trace: arrayMax(a)

Let us follow the count on a = {3, 8, 2, 9, 4}, so n = 5. Table 2.4 shows the variables at each step.

Initially currentMax = a[0] = 3. In iteration 1, a[1] = 8 beats 3 and becomes the maximum; in iteration 2, a[2] = 2 changes nothing; in iteration 3, a[3] = 9 > 8 takes over; in iteration 4, a[4] = 4 is smaller than 9. At i = 5 the condition fails and the method returns 9.

Checking against the table: the condition was tested 5 times (4 true, 1 false), the comparison made 4 times, i++ run 4 times, and there were two updates (8 and 9), so u = 2. The total, 3 · 5 + 1 + 2 = 18, lies between the best-case 16 and the worst-case 20.

The green line in Figure 2.3 also hints at correctness: at the start of every iteration, currentMax is the largest element of the processed part, and when the loop ends that part is the whole array. In 2.4.3 this becomes a proof by loop invariant.

2.2Asymptotic notation

For arrayMax we found between 3n + 1 and 4n operations and kept only “proportional to n.” Every analysis prunes like this, and asymptotic notation does it systematically: it looks at what happens as the input grows very large, setting aside details that matter only for small inputs.

2.2.1Time complexity and Big O

Time complexity expresses an algorithm’s running time as a function of the input size n — the number of elements in an array, characters in a string, vertices and edges in a graph, depending on the problem. We rarely need the function’s exact form, only how it grows.

Big O gives an upper bound. “This algorithm is O(n)” means that for large n its running time stays below some constant multiple of n. Big O is usually applied to the worst case, since an upper bound there is a guarantee for every input — but that is a habit, not part of the definition (2.2.5).

Two classes come up constantly:

• O(1): the operation count does not grow with the input. Reading the first element of an array takes the same steps for three elements or a million. O(1) does not mean identical times, only a bound independent of n.
• O(n): the time grows linearly; doubling n at most roughly doubles it. One pass through an array is O(n).

Even with n only up to 12, the differences in Figure 2.4 are plain: 2ⁿ leaves the chart near n = 6 and n² at n ≈ 7.7, n log n runs clearly above n, and log n is only about 3.6 at 12. Table 2.7 shows how far the gaps open on large inputs.

Big O keeps only the fastest-growing term, dropping constant factors and slower terms:

3n² + 5n + 2 → O(n²)  ·  4n + 100 → O(n)  ·  7 → O(1)

Why is this safe? In the first example, at n = 10 we have 3n² = 300, 5n = 50 and 2, so the quadratic term is 85% of the total; at n = 1000, 3n² = 3,000,000 against 5n = 5000, over 99.8%. The smaller terms’ share tends to zero. The factor 3 depends on the machine and leaves the growth rate alone: doubling n quadruples both 3n² and n².

2.2.2Formal definitions of O, Ω and Θ

Now we make “below a constant multiple for large n” precise. Below, f(n) is the operation count of the algorithm and g(n) a simple comparison function such as n, n² or log n.

Each part has a job. The constant c captures why constant factors don’t matter: c = 3 closes the gap between 3n and n. The threshold n₀ captures why small inputs don’t matter. And “for every n ≥ n₀” demands that the bound hold everywhere past the threshold, not at scattered points.

We will apply all three definitions to f(n) = 2n + 10.

Big O. In Figure 2.5, f starts at 10 and 4n at 0, but 4n is steeper and catches up where 2n + 10 = 4n, at n = 5. For n ≥ 5, 2n + 10 ≤ 4n, so c = 4 and n₀ = 5 show f(n) = O(n). Below 5, f is larger — at n = 2, f = 14 while 4n = 8 — but the definition ignores these values.

Big Omega. For a lower bound, c = 2 works: since 10 is positive, 2n + 10 ≥ 2n for every n (Figure 2.6), so n₀ = 1 and no threshold is needed. f(n) = Ω(n): f grows no slower than n.

Big Theta. Together, 2n ≤ 2n + 10 ≤ 4n for n ≥ 5 (Figure 2.7): f is trapped between lines of slope 2 and 4, so f(n) = Θ(n) — its growth rate is exactly n.

Think of an exam grade. “At most 90” is an upper bound (O), “at least 70” a lower bound (Ω), and together they narrow the grade down. Asymptotically, “at most” and “at least” hold up to constant factors, and when one function serves as both bounds, the growth rate is known exactly (Θ).

Which to write depends on what we know. O is the most common but can be loose: 2n + 10 = O(n²) is true (2n + 10 ≤ n² for n ≥ 5) yet useless, since it hides the real growth. So we give the tightest bound we can, and when it is known, Θ states it most clearly.

2.2.3Using the definition: finding c and n₀

Showing that an expression is in a Big O class means finding a c and n₀. Any pair that works will do. Two approaches are common: bound every term by the largest, or solve the inequality directly.

The first approach works for any polynomial. For n ≥ 1, every term of a degree-d polynomial with nonnegative coefficients is at most a multiple of n^d, so the sum of the coefficients serves as c; the leading coefficient gives the lower bound.

The theorem also holds with negative coefficients (as long as a_d > 0), but n₀ needs more care. For example, n(n − 1)/2 = n²/2 − n/2 is Θ(n²): for n ≥ 2, n/2 ≤ n²/4, so n²/4 ≤ n(n − 1)/2 ≤ n²/2. This expression returns in the analysis of hasDuplicates.

2.2.4Rules of thumb

Hunting for c and n₀ every time would be tiresome. A few rules that follow from the definition do most of the work:

• Drop constant factors. For a constant k > 0, k · f(n) is in the same class as f(n); 5n and n/2 are both Θ(n).
• In a sum, the largest term wins. If f₁ = O(g₁) and f₂ = O(g₂), then f₁ + f₂ = O(max(g₁, g₂)). Consecutive blocks of code combine this way: O(n) + O(n²) = O(n²).
• In a product, the bounds multiply. If f₁ = O(g₁) and f₂ = O(g₂), then f₁ · f₂ = O(g₁ · g₂). This gives nested loops: n outer iterations around log n inner ones cost O(n log n).
• The base of a logarithm doesn’t matter. Since log_a n = log_b n / log_b a, logarithms to different bases differ by a constant factor — for example, log₂ n = log₁₀ n / log₁₀ 2 ≈ 3.32 · log₁₀ n — so we just write O(log n).
• Transitivity. If f = O(g) and g = O(h), then f = O(h); likewise for Ω and Θ.

For n = 1,000,000, log₂ n ≈ 19.9 and log₁₀ n = 6, but the ratio is about 3.32 for every n. When n grows a thousandfold, each grows by a fixed amount: about 10 for log₂, exactly 3 for log₁₀.

Exponentials are different: changing the base changes the growth rate. 3ⁿ / 2ⁿ = 1.5ⁿ grows without bound, so 3ⁿ is not O(2ⁿ). A constant added to the exponent, however, is just a constant factor: 2ⁿ⁺³ = 8 · 2ⁿ = Θ(2ⁿ).

2.2.5Best, average and worst cases

arrayMax needed 3n + 1 operations on a decreasing array and 4n on an increasing one. Most algorithms vary far more, so “the running time” must say which input it means.

Table 2.5 puts the three bounds and the three cases side by side. The top half answers “what kind of bound?”, the bottom half “for which input?” — independent questions.

Linear search checks the elements one by one from the front and stops at the target (code in 2.3.5). Let us work out the three cases for [4, 8, 15, 16, 23, 42], n = 6.

Which case to report depends on the purpose:

• The worst case is a guarantee. “Never more than 4n steps on any input” is reliable information for a system designer, and usually easy to compute — hence the most often reported.
• The average case describes what to expect in practice, but it assumes a probability distribution, misleads when the assumption is wrong, and is often harder to compute.
• The best case alone is misleading. Almost any search is fast when the target happens to sit where it looks first, which says next to nothing about the algorithm in general.

2.2.6Amortized analysis

In some data structures most operations are cheap but an expensive one comes along now and then, and worst-case analysis paints too gloomy a picture. Amortized analysis divides the total cost of a long sequence of operations by the number of operations.

The standard example is an array that grows when full. Java’s ArrayList keeps its elements in an array; adding at the end usually means writing into an empty cell, but when the array is full a new one twice as large is allocated and every element copied over — an O(n) addition.

This is not average-case analysis, which computes an expected cost under a probability distribution. No probability is involved: for every sequence of operations, the worst included, the total is below 3n — a guarantee for the sequence rather than for each operation.

2.2.7Big O classes

Most analyses land in one of a few standard classes, listed in Table 2.6 from slowest- to fastest-growing.

O(log n) algorithms shrink the problem by a constant fraction per step, finishing in about 20 steps even for a million elements. O(n) algorithms look at each element a constant number of times; since reading the input alone takes n steps, many problems allow nothing better. O(n log n) is the class of good sorting algorithms, O(n²) the natural result of comparing every element with every other, and O(2ⁿ) the price of trying every possibility — each increase of n by one doubles the time.

Merge sort’s “log n levels” deserve a word. It splits the array in two, sorts each half the same way, and merges. An array of n elements can be halved log₂ n times before the pieces are single elements, and the merges on each level touch n elements in total: log n levels times n work is n log n.

2.2.8What happens as n grows?

Numbers show the gaps best. Table 2.7 gives each function at three values of n.

Two things stand out. log₂ n barely moves: a hundredfold increase in n takes it only from 3.3 to 10. And 2ⁿ, still reasonable at n = 10 (1,024), is a 31-digit number at n = 100.

Faster hardware cannot rescue an exponential algorithm: a computer a thousand times faster would still need 4 · 10¹⁰ years. A thousandfold speedup lets a 2ⁿ algorithm handle an n only 10 larger in the same time (2¹⁰ ≈ 1000), but a quadratic one an n about 32 times larger (√1000 ≈ 31.6). On large inputs the choice of algorithm matters far more than the hardware.

2.3From code to complexity

Now for the real task: reading a piece of code and stating its complexity. We seldom need to count every operation; what matters is how often the loops run. Loop-free code is O(1), and loops fall into a handful of patterns. We introduce the patterns, then apply them to sum, linear and binary search, duplicate checking and prefix averages.

2.3.1Loop patterns

A loop costs the number of iterations times the cost of one pass through the body; with a constant-cost body, that is proportional to the iteration count. Table 2.8 lists the common patterns, their counts for n = 16, and their classes.

Simple loop. i goes from 0 up by 1 and stops at n: values 0, 1, …, n − 1, so n iterations.

Step of 2. i takes 0, 2, 4, …: n/2 iterations for even n, ⌈n/2⌉ for odd. With a step of 2 or 100, the count is a fixed fraction of n and the loop is O(n); a bigger step speeds it up without changing its class.

Doubling loop. i doubles — 1, 2, 4, 8, … — while below n. After k iterations i = 2^k, so the loop stops the first time 2^k ≥ n, at k = ⌈log₂ n⌉. For n = 16, i is 1, 2, 4, 8 and stops at 16: 4 iterations (traced in 2.3.2). A loop that starts i at n and halves it behaves the same way.

Nested loops. The inner loop runs in full on every outer iteration. If it runs n times regardless of the outer loop, the total is n · n = n². If its bound depends on the outer variable (j < i), we add instead of multiplying: 0 iterations at i = 0, 1 at i = 1, …, n − 1 at i = n − 1, for a total of

0 + 1 + 2 + … + (n − 1) = n(n − 1)/2

This formula is easy to remember: write the sum forward and backward and add the rows term by term — 0 + (n − 1), 1 + (n − 2), … — giving n pairs of n − 1, which is twice the sum. For n = 16, 16 · 15 / 2 = 120. The inner loop averages half the outer count, but the factor 1/2 is dropped and the result is still O(n²).

Consecutive loops. One loop after another adds costs: n + n = 2n, which is O(n) — far cheaper than nesting.

Two general rules follow:

• Consecutive blocks add, and the largest dominates: O(n) + O(n²) = O(n²). A linear scan followed by a nested loop costs what the nested loop costs.
• Nested loops multiply: outer iterations × inner iterations — or, if the inner count depends on the outer variable, the sum over all iterations.

2.3.2Code trace: countSteps(16)

Here is a doubling loop inside a method. countSteps counts how many doublings take 1 up to n:

int countSteps(int n) {
  int k = 0;
  for (int i = 1; i < n; i *= 2)
    k++;
  return k;
}

The counter k starts at 0, i starts at 1 and doubles via i *= 2, and each iteration increments k, so at the end k is the number of iterations.

Figure 2.9 shows why the loop runs so few times: each jump doubles the previous one — 1, 2, 4, 8 — so four jumps reach 16, skipping most of the numbers on the way.

The result, 4, is log₂ 16; in general countSteps(n) returns ⌈log₂ n⌉. It grows very slowly: countSteps(17) = 5, countSteps(1000) = 10, countSteps(16000) = 14. A thousandfold larger n adds only about 10 iterations, because 2¹⁰ = 1024 ≈ 1000. The method is O(log n).

2.3.3Three methods, three classes

Three short methods, each taking an int array and differing only in loop structure:

O(1): the first element.

int first(int[] a) {
    return a[0];
}

No loop: one array access and a return. Indexing computes the address directly — start address plus index times element size — regardless of the array’s length. The method is O(1).

O(n): the sum.

int sum(int[] a) {
    int s = 0;
    for (int x : a)  // n times
        s += x;
    return s;
}

for (int x : a) is the enhanced for (for-each) loop: x takes each element in turn. The body — one addition, one assignment — runs n times; the code outside the loop is constant. The method is O(n).

O(n²): checking for duplicates.

boolean hasDuplicates(int[] a) {
    for (int i = 0; i < a.length; i++)
        for (int j = i + 1; j < a.length; j++)
            if (a[i] == a[j])
                return true;
    return false;
}
// outer loop n, inner loop ≈ n/2
// → n(n−1)/2 comparisons

For each index i, the inner loop compares a[i] with every element to its right, starting at j = i + 1. That start ensures no element is compared with itself and each pair only once (after a[0] vs a[3], there is no a[3] vs a[0]). The method returns true at the first equal pair, false if there is none.

In the worst case, with no duplicates, the inner loop runs n − 1 times for i = 0, n − 2 for i = 1, …, once for i = n − 2, and not at all for i = n − 1:

(n − 1) + (n − 2) + … + 1 + 0 = n(n − 1)/2 = n²/2 − n/2

Dropping constants and the smaller term gives O(n²): about n/2 inner iterations times n outer ones is still quadratic. This is also the number of distinct pairs among n elements, so any algorithm that examines every pair makes at least this many comparisons.

The best case finds a match at once: if a[0] == a[1], one comparison suffices, Θ(1) — exactly the array of zeros in 2.1.3.

2.3.4Code trace: sum()

Tracing sum together with its caller also shows how a method call proceeds.

int sum(int[] a) {
    int s = 0;
    for (int x : a) {
        s += x;
    }
    return s;
}

// in main:
System.out.println(sum(a));

Let a = {7, 2, 9} in main. Calling sum(a) pushes a new stack frame holding the parameters and locals (s, x). The parameter a refers to the same array as in main: a Java array variable is a reference holding the array’s location, and only the location is passed, so the call costs the same for any array size.

The body ran n = 3 times. Pushing the frame, initializing s, returning and printing do not depend on the array size; with 3 million elements only the iteration count would change. The time has the form c₁ · n + c₂: O(n).

2.3.5Linear search

Linear search, the simplest way to find a value, examines the elements in order from the front.

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

Each iteration compares a[i] with the target; on a match the method returns i at once. If the loop finishes, the target is absent and the method returns -1, which, not being a valid index, means “not found.”

We trace it on a sorted array, a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} (n = 10), with target 23.

The target took 6 comparisons. Linear search ignores the fact that the array is sorted: learning that 2 is less than 23 says nothing about the other elements, so each step rules out one element (Figure 2.10). A target that is last or absent (say 40) would cost all 10 comparisons.

The analysis matches Example 2.3: best case (target first) 1 comparison, Θ(1); worst case (last or absent) n, Θ(n); average with equally likely positions (n + 1)/2, also Θ(n). With only a few variables, the extra space is O(1).

Linear search’s strength is that it needs no sorting, and on an unsorted array nothing is faster: we cannot rule out an element without looking at it, so the worst case must examine them all.

2.3.6Binary search

A sorted array allows much better. Nobody searches a phone book from page one: we open it in the middle, set aside the half that cannot contain the name, and repeat on the rest. Binary search is this method as an algorithm.

int binarySearch(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

• lo and hi bound the range that could hold the target, initially the whole array: lo = 0, hi = a.length - 1.
• while (lo <= hi): the search continues while the range is nonempty; lo > hi means it is empty.
• mid = (lo + hi) / 2 is the middle index. Integer division in Java discards the fraction: (0 + 9)/2 = 4.
• If a[mid] == target, mid is returned.
• If a[mid] < target, the sorted order puts the target right of mid: lo = mid + 1 discards the left half, middle included.
• Otherwise a[mid] > target and the target can only be to the left: hi = mid - 1.
• If the loop ends, -1 is returned.

The power lies in one comparison discarding half the range. In linear search, a[i] ≠ target rules out one element; in binary search, a[mid] < target tells us, thanks to the sorted order, that everything left of mid is smaller too.

Same array, same target: a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, target 23.

In iteration 1, mid = (0 + 9)/2 = 4 and a[4] = 16 is less than 23, so lo = 5: five elements gone in one comparison. In iteration 2, mid = (5 + 9)/2 = 7 and a[7] = 56 is too large, so hi = 6. In iteration 3, mid = (5 + 6)/2 = 5 and a[5] = 23: found.

Three iterations against linear search’s six comparisons, the range halving each time — 10, 5, 2. A twofold gain on this small array becomes dramatic on large ones.

2.3.7The worst case of binary search

The worst case is an absent target, which shrinks the range all the way down. Let us search the same array for 40, which would lie between 38 and 56.

The first two iterations match the search for 23. In iteration 3, a[5] = 23 is too small, so lo = 6, leaving only 38 at index 6. In iteration 4, 38 is too small as well, so lo = 7. Now lo = 7 > hi = 6 (Figure 2.12), the loop ends, and the method returns -1.

As a bonus, the final lo is where the target would be inserted: 40 belongs between 38 (index 6) and 56 (index 7), at index 7. Some algorithms for inserting into sorted arrays exploit this.

Even the worst case took just 4 iterations, against 10 comparisons for linear search. The following theorem explains why.

Let the range hold m elements. An unsuccessful iteration keeps only the part left or right of mid, and discards the middle too, so at most ⌊m/2⌋ elements remain. Starting from n and at least halving each time, at most ⌊n/2^k⌋ remain after k iterations — zero once 2^k > n. So after k = ⌊log₂ n⌋ + 1 iterations the range is certainly empty.

For n = 10, ⌊log₂ 10⌋ + 1 = 3 + 1 = 4, and the counts went 10 → 5 → 2 → 1 → 0. Table 2.14 compares the worst cases of the two searches for several sizes.

For a million sorted elements, binary search needs at most 20 iterations where linear search may need a million comparisons — a factor of fifty thousand that widens as n grows. The price is keeping the array sorted, easily paid when it is sorted once and searched many times.

2.3.8Code trace: hasDuplicates()

Now we trace hasDuplicates from 2.3.3 on a = {4, 7, 1, 7}, where 7 appears twice.

boolean hasDuplicates(int[] a) {
    for (int i = 0; i < a.length; i++)
        for (int j = i + 1; j < a.length; j++)
            if (a[i] == a[j])
                return true;
    return false;
}

With i = 0, a[0] = 4 is compared with the three elements to its right, none equal. With i = 1, the inner loop starts at j = 2: a[1] = 7 is compared with 1, then with a[3] = 7 — a match, so the method returns true on the fifth comparison, and the i = 2 iteration never runs.

Without duplicates — for {4, 7, 1, 9}, say — all pairs would be compared: n(n − 1)/2 = 4 · 3 / 2 = 6 comparisons. This O(n²) worst case is why the times in Table 2.2 roughly quadrupled with each doubling.

We can do better: after sorting, equal elements are neighbors, so O(n log n) for the sort plus an O(n) scan suffices. The next example turns a quadratic algorithm into a linear one another way: by cutting redundant work.

2.3.9The prefix averages problem

How different can two algorithms for the same problem be in cost? A concrete problem answers that (Goodrich et al., Section 4.3).

A “prefix” is a part that starts at the beginning, x[0..j], and we want every prefix’s average. Examples abound: a stock’s average daily price since January, a student’s grade average since the start of term. Moving averages and financial trend analysis rest on similar calculations.

There is a repetition here: 18, the numerator of a[2], is just 12, the numerator of a[1], plus x[2] = 6. The two solutions differ on exactly this point. The first recomputes each sum from scratch and takes O(n²); the second carries the sum forward and takes O(n).

2.3.10prefixAverage1: summing from scratch

double[] prefixAverage1(double[] x) {
  int n = x.length;
  double[] a = new double[n];
  for (int j = 0; j < n; j++) {
    double total = 0;
    for (int i = 0; i <= j; i++)
      total += x[i];
    a[j] = total / (j + 1);
  }
  return a;
}

• a = new double[n] allocates the result array, which Java fills with 0.0.
• The outer loop computes one prefix average per j.
• double total = 0 sits inside the outer loop, so the sum restarts from zero for every j.
• The inner loop adds x[0] through x[j] to total. The condition is i <= j; with <, x[j] would be left out.
• a[j] = total / (j + 1) stores the average; total is a double, so the fraction is kept.

Table 2.16 shows every inner iteration for x = [4, 8, 6, 2].

The third column exposes the weakness: x[0] = 4 is added four times, x[1] = 8 three times, x[2] = 6 twice. Each iteration forgets the previous sum and redoes the same additions.

Iteration j runs the inner loop j + 1 times, so the total number of additions is

1 + 2 + … + n = n(n + 1)/2

For n = 4 that is 4 · 5 / 2 = 10, the 1 + 2 + 3 + 4 of the table. The expression n²/2 + n/2 is Θ(n²) by Theorem 2.1. The extra space is O(n), for the result array a.

2.3.11prefixAverage2: a running sum

The cure is to carry the sum forward: the sum of prefix j is the sum of prefix j − 1 plus x[j].

double[] prefixAverage2(double[] x) {
  int n = x.length;
  double[] a = new double[n];
  double total = 0;
  for (int j = 0; j < n; j++) {
    total += x[j];
    a[j] = total / (j + 1);
  }
  return a;
}

Two small changes decide everything: double total = 0 has moved outside the loop, so the sum persists, and the inner loop has become the single line total += x[j], which turns the sum of x[0..j−1] into the sum of x[0..j].

The result, [4.0, 6.0, 6.0, 5.0], matches prefixAverage1, with 4 additions instead of 10. Each of the n iterations does one addition, one division and one assignment, so prefixAverage2 runs in Θ(n) time, again with O(n) extra space for the result.

2.3.12Comparing the two solutions

Here are the addition counts side by side:

At n = 10 the factor of 5.5 may seem minor. At n = 10⁶, though, prefixAverage1 performs about 5 · 10¹¹ additions against 10⁶; at 10⁹ additions per second, that is about 500 seconds (over 8 minutes) versus 1 millisecond. The ratio, (n + 1)/2, keeps growing with n.

The gap comes from removing repeated work: prefixAverage2 remembers the previous sum, prefixAverage1 forgets it and starts over. Saving a result and reusing it underlies many efficient algorithms, and the first step in speeding one up is often to ask: “Am I doing the same work more than once?”

Both use the same space — an n-cell result array and a few variables — so the speedup cost no memory.

2.4Space, correctness and robustness

So far we have measured only time. Three criteria of a good algorithm remain (2.1.2): memory, correctness and robustness. Memory is measured with the same tools as time; correctness and robustness are demonstrated and tested.

2.4.1Space complexity

Space complexity describes how an algorithm’s memory use grows with the input size, in Big O, with constants and smaller terms dropped.

The input itself is usually not counted. The array passed to arrayMax was in memory before the call; the method’s own memory is just currentMax and i. Memory used beyond the input is extra space, and this is what analyses usually measure — though they should say whether the input is counted.

Figure 2.18 shows the three basic classes:

• O(1), constant space: a few variables, independent of the input size. arrayMax, sum, linearSearch, binarySearch and hasDuplicates use only such variables (the maximum, the sum, indices, lo, hi, mid).
• O(n), linear space: a new array the size of the input, like the result array a of prefixAverage1 and prefixAverage2.
• O(n²), quadratic space: an n × n matrix, such as a table of distances between n cities. For n = 10,000 that is a hundred million cells — about 400 MB of 4-byte ints.

Memory efficiency matters most on constrained systems — embedded devices, phones, servers handling thousands of requests at once — but no memory is unlimited, and a quadratic-space algorithm exhausts even the largest machine once n is big enough.

An easily overlooked item is the call stack. Each call pushes a frame (2.3.4) that stays until the method returns. A loop uses one frame, but a method that calls itself — a recursive method — has as many frames open as its call depth. A recursion n levels deep uses O(n) extra space without allocating a single array.

2.4.2Correctness

A fast algorithm with wrong results is worthless, so correctness comes before cost.

“Every valid input” is the crux: inputs are infinite and cannot all be tried. Four tools help:

• Test cases. Run the algorithm on inputs with known answers — arrayMax({3, 8, 2, 9, 4}) must return 9. Tests are excellent at finding bugs but prove nothing: an untested input may still fail.
• Edge cases. Bugs hide at the boundaries. Always try an empty input, a single element, extreme values, identical elements, and sorted or reverse-sorted arrays. For arrayMax: a one-element array, the maximum at the front, back and middle, and all-negative numbers.
• Loop invariant. A property that holds on every iteration, from which correctness is proved for all inputs, unlike testing (2.4.3).
• Counterexample. A single input proves an algorithm wrong. Correctness is a claim about all inputs; incorrectness needs just one.

2.4.3Proof by loop invariant

A test says “it works on these inputs”; a proof says “it works on every input.” For loops, the handiest proof tool is the loop invariant.

This is induction in disguise: initialization is the base case, maintenance the inductive step, and termination links the statement to the result.

Proof. The invariant: at the start of each iteration, currentMax is the largest of a[0..i−1].

• Initialization. Before the first iteration, i = 1 and currentMax = a[0], the largest (and only) element of a[0..0].
• Maintenance. Suppose currentMax is the largest of a[0..i−1]. If a[i] is larger, currentMax = a[i], which beats the old maximum and so all earlier elements: it is the largest of a[0..i]. Otherwise currentMax is unchanged and, being at least a[i], remains the largest of a[0..i]. After i++, this reads “the largest of a[0..i−1].”
• Termination. i grows by 1 per iteration and the loop stops at i = n, so it ends in finite time, and the invariant then says currentMax is the largest of a[0..n−1] — the whole array. The method returns it. ∎

Figure 2.19 shows the invariant for {3, 8, 2, 9, 4} at i = 3: currentMax = 8 is the maximum of the green part, a[0..2] = {3, 8, 2}; the next element, 9, is larger, so the iteration ends with currentMax = 9, the maximum of a[0..3].

The theorem requires “at least one element”: an empty array has no a[0], and initialization fails. This is not a gap in the proof but a precondition of the method; what should happen when it is violated is a question of robustness.

2.4.4Robustness

Correctness concerns valid inputs, but real programs also meet invalid ones: an empty file, a missing line, a malformed number. Robustness is the ability to cope with them. A robust algorithm neither crashes nor silently produces a wrong result outside the normal range; it either handles the input sensibly or reports the problem clearly.

Robustness is tested from four angles:

Each is a real source of failures. Given an empty array, arrayMax throws ArrayIndexOutOfBoundsException at a[0]; given null, NullPointerException. Either stops the program, but neither message states the cause. The binary search overflow (2.3.7) is a large-data robustness problem: flawless on small arrays, broken beyond a billion elements.

A robust version checks its precondition and reports violations clearly:

int arrayMaxChecked(int[] a) {
  if (a == null || a.length == 0)
    throw new IllegalArgumentException("Array must not be empty");
  int currentMax = a[0];
  for (int i = 1; i < a.length; i++)
    if (a[i] > currentMax)
      currentMax = a[i];
  return currentMax;
}

The first line catches both invalid cases. a == null comes first, and || skips its right side when the left is true, so the length of a null array is never read. Invalid input raises IllegalArgumentException with a message saying what is wrong; the rest is identical to arrayMax.

The check costs at most two comparisons, O(1), and the method stays Θ(n). Robustness is often this cheap, so checking preconditions is a good habit, especially in methods others will call.

What to do with an empty array is a design decision: throw an exception, or return a special value — Java’s OptionalInt exists for this. The one wrong choice is a silent, meaningless value, like the 0 that the faulty version in Example 2.9 returns, leading the caller to believe the array’s largest element is 0.

2.5Common mistakes

Table 2.20 collects the chapter’s most important mistakes.

The array comparison mistake is common when testing methods like hasDuplicates. After int[] a = {1, 2}; int[] b = {1, 2};, a == b is false: the variables refer to two separate arrays, and == asks “same array?”, not “same contents?”. Arrays.equals(a, b) compares element by element and returns true, in O(n) time; == compares two references in O(1).

The lesson of “O(1) is always fast” applies to every class. A linear algorithm of 1000n steps beats a quadratic one of n² steps only when n > 1000; below that the quadratic one is faster. Asymptotic analysis says which wins as inputs grow; for small inputs, the constants matter too.

2.6Summary

• An algorithm is a method of finite, precise and effective steps that is correct for every valid input, judged by time, space, correctness and robustness.
• Empirical analysis times code with System.nanoTime(), taking the median of repeated runs after a warm-up. In a doubling experiment, T(2n)/T(n) ≈ 2^k means T(n) ≈ c · n^k. It depends on hardware, covers only the inputs tried, and needs complete code.
• Counting primitive operations is hardware-independent and valid for all inputs. arrayMax performs 3n + 1 operations at best and 4n at worst, both Θ(n).
• f(n) = O(g(n)): for some c > 0 and n₀, f(n) ≤ c · g(n) for every n ≥ n₀ (upper bound); Ω is a lower bound, Θ both (tight bound). Constant factors and smaller terms are dropped, a degree-d polynomial is Θ(n^d), and the base of a logarithm doesn’t matter.
• Best, average and worst case specify which input’s cost we study, independently of the bound notations. The worst case is a guarantee, the average case assumes a distribution, the best case alone misleads. Amortized analysis divides the total cost of a long sequence by its length; adding to a growable array is amortized O(1).
• Common classes, slowest-growing first: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ). At 10⁹ operations per second, 2ⁿ steps for n = 100 take about 4 · 10¹³ years.
• Loop patterns: single loop O(n); doubling or halving loop O(log n); two full nested loops O(n²); n outer around log n inner O(n log n). Consecutive blocks add; nested loops multiply.
• Linear search is O(n) and needs no sorting. Binary search halves the range of a sorted array each iteration, making at most ⌊log₂ n⌋ + 1 iterations: O(log n). Compute the middle as lo + (hi - lo) / 2.
• hasDuplicates compares all pairs: n(n − 1)/2 comparisons in the worst case, O(n²). For prefix averages, prefixAverage1 re-sums each prefix with n(n + 1)/2 additions, O(n²); prefixAverage2 carries the sum with n additions, O(n).
• Space complexity usually measures extra memory: a few variables O(1), a new array O(n), an n × n matrix O(n²). Recursion also counts the call stack.
• Correctness is shown with tests, edge cases and loop invariants (initialization, maintenance, termination); one counterexample proves an algorithm wrong. A robust algorithm detects invalid input and reports it clearly.

These tools will be used to compare the operations of every data structure that follows. Table 2.22 previews the costs of common operations on structures covered later in the course, to show how differently the same operation can cost.

The first row ties back to this chapter. Accessing the ith element is an address computation, as in first: O(1). Searching an unsorted array is linear search, O(n); a sorted array allows binary search in O(log n). Inserting or deleting in the middle shifts the elements that follow: O(n).

2.7Key terms

Each term links to the course glossary, which gives its Turkish equivalent and its use in other chapters.

• algorithm
• algorithm analysis
• complexity
• time complexity
• space complexity
• empirical analysis
• doubling experiment
• primitive operation
• asymptotic
• Big O
• Big Omega
• Big Theta
• best case
• average case
• worst case
• amortized analysis
• loop
• linear search
• binary search
• prefix averages
• stack frame
• reference
• correctness
• invariant
• robustness

2.8Test Yourself

1. How many times is currentMax updated in arrayMax({5, 1, 7, 7, 2})? With the counting rules of Table 2.3, how many primitive operations are performed?

   Answer

   1 > 5 false, 7 > 5 true (update), 7 > 7 false, 2 > 7 false: a single update, u = 1, since the second 7 is only equal. Total 3n + 1 + u = 3 · 5 + 1 + 1 = 17.

2. For f(n) = 4n + 7, give c and n₀ showing f(n) = O(n). Is f(n) = Θ(n)?

   Answer

   With c = 5, 4n + 7 ≤ 5n for n ≥ 7, so n₀ = 7 (c = 11, n₀ = 1 also works). Since 4n + 7 ≥ 4n for every n ≥ 1, f(n) = Ω(n), and together f(n) = Θ(n).

3. Which are true? (a) n² + 100n = O(n²) (b) 2ⁿ⁺¹ = O(2ⁿ) (c) n log n = O(n) (d) 4ⁿ = O(2ⁿ) (e) log₁₀ n = Θ(log₂ n)

   Answer

   (a), (b) and (e). (a): n² + 100n ≤ 101n² for n ≥ 1. (b): 2ⁿ⁺¹ = 2 · 2ⁿ, a constant factor. (e): the logarithms differ by a constant factor. (c) is false: n log n / n = log n grows without bound. (d) is false: 4ⁿ / 2ⁿ = 2ⁿ grows without bound.

4. How many iterations does for (int i = 1; i <= n; i *= 3) s++; make for n = 81? What is its complexity?

   Answer

   i is 1, 3, 9, 27, 81 (the condition is <=, so 81 counts), then 243 ends the loop: 5 iterations, log₃ 81 + 1. O(log n); base 3 does not change the class.

5. What is s after this code with n = 10? What is the complexity?

   for (i = 0; i < n; i++) for (j = 0; j < 5; j++) s++;
for (k = 0; k < n; k++) for (m = 0; m < k; m++) s++;

   Answer

   First block: 10 outer times a fixed 5 inner, 50; O(n). Second: 0 + 1 + … + 9 = 10 · 9 / 2 = 45; O(n²). So s = 95, and the larger block dominates: O(n²).

6. For a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, how many iterations do binarySearch(a, 91) and binarySearch(a, 2) make? Give lo, hi and mid for each.

   Answer

   For 91: (0, 9, mid 4, 16 < 91) → lo = 5; (5, 9, 7, 56) → lo = 8; (8, 9, 8, 72) → lo = 9; (9, 9, 9, 91) found, returns 9. 4 iterations. For 2: (0, 9, 4, 16 > 2) → hi = 3; (0, 3, 1, 5 > 2) → hi = 0; (0, 0, 0, 2) found, returns 0. 3 iterations. Both are within ⌊log₂ 10⌋ + 1 = 4.

7. Linear search runs on 9 elements. If the target is always present and equally likely at each position, how many comparisons are made on average? How many if it is absent?

   Answer

   A target at position k (from 1) costs k comparisons, so the average is (1 + 2 + … + 9)/9 = 45/9 = 5, matching (n + 1)/2. An absent target costs all 9.

8. A doubling experiment gives 40, 81, 160 and 322 ms for n = 1000, 2000, 4000 and 8000. What is the growth class? About how long will n = 16,000 take?

   Answer

   The ratios 81/40 ≈ 2.03, 160/81 ≈ 1.98, 322/160 ≈ 2.01 give 2^k ≈ 2, so k = 1: linear. n = 16,000 should take about 2 · 322 = 644 ms.

9. A student starts arrayMax with currentMax = 0 and loops from i = 0. Give a counterexample. Which invariant fails at initialization?

   Answer

   {-4, -2, -9} returns 0 instead of −2. The invariant “at the start of each iteration, currentMax is the largest of a[0..i−1]” fails: initially i = 0, a[0..−1] is empty and has no largest element, and 0 is not in the array. With initialization broken, the proof collapses and arrays of negative numbers give wrong results.

10. What is the extra space of each? (Input not counted.) (a) sum (b) prefixAverage1 (c) a method that builds, from an n-element array, the n × n matrix of a[i] + a[j] for every pair (i, j) (d) countSteps

    Answer

    (a) O(1): just s and x. (b) O(n): the result array a. (c) O(n²): n² cells. (d) O(1): just k and i.

2.9Further reading

• M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Data Structures and Algorithms in Java (6th ed., 2014), Chapter 4: empirical analysis, counting primitive operations, Big O, Omega and Theta, and the prefix averages example, in an order close to these notes and with Java code.
• R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Section 1.4: the doubling experiment and predicting running time from observations, with detailed examples of empirical and mathematical analysis working together.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (4th ed., 2022), Chapters 2 and 3: correctness proofs by loop invariant and the formal definitions of asymptotic notation, in more mathematical language.
• J. Bloch, “Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken” (Google Research Blog, 2006): a short account of how the middle-index overflow surfaced in real software.

2.10References

1. J. Bloch, “Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken”, Google Research Blog, June 2, 2006.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022.
3. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6th ed., Wiley, 2014.
4. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.

Related pages: Chapter 2 slides · Study questions · Glossary · © Sercan Külcü. All rights reserved.