← Back to Subjects ororo.world

Chapter 14: Complexity and Big O Notation

A school office keeps its student records in a single file. A student writes a small Java program to sort that file by name, tests it on the forty entries of one class, and finds that it finishes before the cursor has stopped blinking. The same program is then handed the register of the whole school — about four thousand entries — and it takes noticeably longer. Handed a district-level list of four hundred thousand entries, it does not finish at all in any reasonable time. Nothing about the program has changed. Nothing is wrong with the machine. What has changed is the amount of work the method itself demands as the list grows.

The tool used to describe that growth is older than the computer. The symbol O was introduced in 1894 by the German mathematician Paul Bachmann in a book on number theory, and was made widely known by Edmund Landau soon after. It sat quietly in mathematics for decades until computer scientists — Donald Knuth foremost among them — recognised that it answered exactly the question programmers kept asking: not how long a program took on one afternoon on one machine, but how its cost would grow when the data grew.

Diagram

Fig. 14.0-1 – graph with input size n on the horizontal axis and number of steps on the vertical axis; two curves drawn from the origin, one a straight line labelled “n steps” rising gently, one a steep upward curve labelled “n² steps”; a dashed vertical line at a marked point on the axis showing the gap between the two curves at that input size; both curves labelled at their right-hand ends

This chapter answers the questions below.

NoteCuriosity Corner

Q1. Why does a program that is quick on a hundred records become unusable on a hundred thousand, even when it is run on a much faster computer? Q2. Why do we count the steps an algorithm takes instead of simply timing it with a clock? Q3. If a method takes \(3n^2 + 50n + 200\) steps, why is only the \(n^2\) part reported as its cost? Q4. One method must look at every element of a list; another can throw away half the list at each step. On a list of a million entries, how large is the difference between them? Q5. Bubble sort, selection sort and insertion sort all need roughly \(n^2\) comparisons in the worst case. Is there any reason left to prefer one of them over another?

14.1 Why the Cost of an Algorithm Matters

You have spent this year learning to write programs that produce the right answer. Correctness is the first demand, and nothing replaces it. But a program that gives the right answer after four hours is of no use to an office that needs the answer before the counter closes.

So a second question sits beside the first: not only does this method work, but what does it cost to run. That question has a precise answer, and the answer can be worked out on paper, before the program is ever typed in.

An algorithm is a finite, ordered set of unambiguous steps that takes some input and produces the required output. Computational complexity is the study of what an algorithm costs to carry out — how much work it demands and how that demand grows as the data grows.

14.1.1 Two Programs for the Same Task

Consider a task you can solve in two very different ways: finding the sum of the first \(n\) natural numbers.

One method is the obvious one. Start a running total at zero and add \(1, 2, 3, \ldots, n\) to it in turn. The other method uses the standard result that this sum equals \(n(n+1)/2\), so a single expression gives the answer with no repetition at all.

Both methods are correct. Both produce the same number for every \(n\). The program below implements each as a separate method so that they can be compared side by side.

two methods for the sum of the first n natural numbers Problem: For a value of \(n\) fixed in the program, compute the sum \(1 + 2 + \cdots + n\) twice — once by repeated addition and once by the formula \(n(n+1)/2\) — and display both results.

class SumCompare
{
    static long sumByLoop(int n)
    {
        long total = 0;
        for (int i = 1; i <= n; i++)
        {
            total = total + i;
        }
        return total;
    }

    static long sumByFormula(int n)
    {
        return (long)n * (n + 1) / 2;
    }

    public static void main(String args[])
    {
        int n = 100;
        System.out.println("n = " + n);
        System.out.println("Sum by loop    = " + sumByLoop(n));
        System.out.println("Sum by formula = " + sumByFormula(n));
    }
}

Sample output:

n = 100
Sum by loop    = 5050
Sum by formula = 5050

Variable description:

[Table:] Table 14.1 – variable description for the program SumCompare, listing each variable, its type and its purpose | Variable | Type | Purpose | |—|—|—| | n | int | The count of natural numbers to be added; the input size of the task | | total | long | Running total inside sumByLoop(), holding the sum built up so far | | i | int | Loop control variable, taking the values 1 to n in turn | [/Table]

Notes: The return type is long rather than int because the sum grows quickly with n and would overflow an int for large inputs. In sumByFormula(), the cast (long)n is applied before the multiplication so that the product n * (n + 1) is itself computed in long arithmetic. The two methods are deliberately written to the same specification so that only their working differs.

Now count the work, not the time. In sumByLoop(), the addition inside the loop body is performed once for every value of i from 1 to n — that is, \(n\) times — and the loop control does a comparison and an increment each time round as well. In sumByFormula(), one addition, one multiplication and one division are performed, and that is all, whatever the value of n.

Table 14.2 – number of additions performed inside each method for four values of n

Value of n Additions in sumByLoop() Arithmetic operations in sumByFormula()
10 10 3
100 100 3
1000 1000 3
100000 100000 3

Read down the two columns. The first grows exactly in step with \(n\); the second does not grow at all. This is the whole idea of complexity in miniature: the cost of a method is not a single number but a pattern of growth, and two methods that agree on every answer can disagree completely on cost.

sumByLoop() called with n = 5

Iteration Value of i at entry total before addition total after addition
1 1 0 1
2 2 1 3
3 3 3 6
4 4 6 10
5 5 10 15

Result: the method returns 15. The trace shows that the loop body ran exactly five times for \(n = 5\) — one execution per value added — which is the counting rule the table above is built on.

The cost belongs to the method

Notice what the count did not depend on. It did not depend on the make of the computer, on the amount of memory installed, on whether the program was run in BlueJ or from the command line, or on how many other windows were open. Those things change how long a step takes. They do not change how many steps the method demands. That number is a property of the method itself, and it can be worked out by reading the code.

14.1.2 Input Size

Every statement about cost is a statement about something growing. Before a cost can be quoted, it must be clear what is growing.

The input size is the measure of how much data the algorithm is given, written as a number, usually called \(n\). For a method that processes an array, \(n\) is normally the number of elements in the array. For a method that examines a string, \(n\) is its length. For the summing methods above, \(n\) is the value supplied, since that is what fixes how many numbers are to be added.

NoteDefinition

The input size of an algorithm is a single number, written \(n\), that measures the amount of data the algorithm has to work on. Every statement of complexity is a statement about how the work grows as \(n\) grows, and is meaningless until it is said what \(n\) counts.

Saying what \(n\) counts is not a formality. “This method takes \(n\) steps” is an incomplete claim; “this method takes \(n\) steps, where \(n\) is the number of elements in the array” is a complete one. Throughout this chapter, every cost is quoted with its \(n\) named.

Q. A method receives an array of String values and joins them into one long line. Two quantities could be called the input size here. Which is which?

A. The number of strings in the array is one measure; the total number of characters across all the strings is another. Both are legitimate, and they behave differently — an array of 10 very long strings and an array of 1000 short ones may have the same character count. You must state which one you are calling \(n\) before quoting any cost.

14.1.3 Counting Operations Rather Than Seconds

It is tempting to settle the question by experiment: run both methods, note the time each takes, and declare a winner. Java even makes the timing easy. The trouble is that the number obtained describes the afternoon, not the algorithm.

judging an algorithm by timing one run What students write:

long start = System.currentTimeMillis();
sumByLoop(1000);
long end = System.currentTimeMillis();
System.out.println("Time = " + (end - start));

What happens: on most machines this prints 0, because a thousand additions finish well inside a single tick of the clock. Run on a different machine, or on the same machine while other programs are busy, it prints something different again. Nothing has been learnt about the method. The fix: count the operations the method performs, expressed as a function of the input size. That count is the same on every machine, and it can be obtained by reading the code rather than by running it.

A faster machine helps, but only in one particular way. Suppose one computer performs each step in half the time of another. Then every algorithm run on it finishes in half the time — the step count is untouched, and each step is simply cheaper. In Fig. 14.1-1 the same eight steps are shown running on a slower and a faster machine.

Diagram

Fig. 14.1-1 – two side-by-side panels showing the same algorithm on the same input; each panel contains an identical vertical column of eight labelled step boxes, Step 1 to Step 8; left panel headed “slower machine – 2 time units per step – total 16 units”, right panel headed “faster machine – 1 time unit per step – total 8 units”; a single caption line beneath both panels reading “the number of steps is unchanged; only the time per step differs”

Hardware buys you a constant multiplier. Growth is a different thing altogether. If one method needs \(n\) steps and another needs \(n^2\) steps, then at \(n = 1000\) the second needs a thousand times as many steps as the first, at \(n = 100000\) it needs a hundred thousand times as many, and no fixed multiplier from better hardware can close a gap that widens without limit.

Q1. Why does a program that is quick on a hundred records become unusable on a hundred thousand, even when it is run on a much faster computer?

A. Because the two things being compared are not the same kind of quantity. A faster computer divides the time per step by a fixed factor — perhaps two or ten — and that factor is the same at every input size. Increasing the data multiplies the number of steps, and for many methods it multiplies it far more than it multiplies the data. A method that needs \(n^2\) steps needs a million times as many steps at a hundred thousand records as at a hundred, and a machine ten times faster cancels only ten of that million.

Q2. Why do we count the steps an algorithm takes instead of simply timing it with a clock?

A. A measured time belongs to one run of one program on one machine under one set of conditions, and changes when any of those change. A step count belongs to the algorithm. It can be worked out from the code before the program is run, it holds on every machine, and it tells you what will happen at input sizes you have not yet tested — which is exactly the information a timing on today’s small test data cannot give you.

14.1.4 Time Complexity and Space Complexity

An algorithm consumes two resources worth measuring: the work it does, and the memory it occupies. Complexity is quoted separately for each.

Time complexity measures the number of steps an algorithm performs, as a function of the input size. It is a count of operations, not a measurement in seconds, for the reasons just given.

NoteDefinition

The time complexity of an algorithm is the number of basic operations it performs, expressed as a function of the input size \(n\).

Space complexity measures the amount of memory the algorithm needs beyond the input itself, again as a function of the input size. A useful picture is the rough paper you use while working a problem by hand: the question is not how much paper the question is printed on, but how many extra sheets the method makes you fill.

NoteDefinition

The space complexity of an algorithm is the amount of memory it requires, expressed as a function of the input size \(n\).

Both sumByLoop() and sumByFormula() use a fixed handful of variables whatever the value of n, so neither needs extra memory that grows with the input. Their space costs are identical; only their time costs differ. That is common enough, but not universal — a method that copies an array into a second array of the same length needs memory that grows in step with \(n\), while one that rearranges the array in place does not.

Table 14.3 – Time complexity vs Space complexity

Feature Time complexity Space complexity
What is measured Number of operations performed Amount of memory occupied
Unit of the count Basic operations such as a comparison, an assignment or an arithmetic operation Storage cells such as variables and array elements
Depends on the machine No — the count is fixed by the algorithm No — the count is fixed by the algorithm
Typical way it grows With the number of times a loop body is entered With the number of extra variables or array cells created
Reduced by Doing less repeated work Reusing storage instead of making copies

The two can be traded against each other. A method can often be made faster by storing results it would otherwise recompute, which costs memory; it can be made to use less memory by recomputing values instead of keeping them, which costs time. Recognising that trade is part of choosing an algorithm rather than merely writing one.

For the rest of this chapter the discussion is about time complexity, because that is where the differences between standard algorithms are sharpest, and where the growth patterns are easiest to establish by counting. Where a method’s memory demand is unusual, it is mentioned separately.

Take the two methods of SumCompare and, without running the program, write down how many times the addition inside sumByLoop() is performed for n equal to 8, 80 and 800. Then change the value of n in main() to each of these and confirm that both methods still print the same sum. Note whether your predicted counts and the printed answers ever disagree.

14.2 Estimating Complexity in Terms of Methods

A method is built out of a small number of construct types: plain statements, statements placed one after another, conditionals, loops, and loops inside loops. If you know what each of these costs, you can read any method and write down its cost without running it.

The procedure is always the same. Decide what \(n\) counts. Go through the method construct by construct, asking of each statement how many times it is executed when the method is called on input of size \(n\). Add the counts. What comes out is a formula in \(n\).

A basic operation is a single elementary action that the machine performs in a fixed amount of time — one comparison, one assignment, one arithmetic operation, one array access. Counting basic operations is what makes the estimate independent of the machine.

14.2.1 Simple Statements

A statement that does a fixed amount of work, no matter how large the input is, runs in constant time. An assignment, an arithmetic expression, a comparison, reading one element of an array — each of these takes the same effort whether the array holds ten values or ten million.

int mid = (low + high) / 2;

This performs one addition, one division and one assignment. Three basic operations, always three, whatever \(n\) may be.

NoteDefinition

A statement runs in constant time when the number of basic operations it performs does not depend on the input size \(n\) — that is, the count stays the same as \(n\) grows.

There is one trap here, and it is worth naming early. A statement that looks simple may not be. A call such as arrangeInOrder(marks) occupies one line, but its cost is the cost of whatever that method does, which may be very large. When you count, a method call costs what the method costs, not one operation. Only calls whose bodies you have already established as constant time may be counted as one.

14.2.2 Consecutive Statements

When statements follow one another, each is executed once and their costs add.

int a = 0;
int b = a + 5;
System.out.println(b);

Three constant-time statements one after another give a constant total. Nothing has grown, so the whole block is still constant time.

The same addition rule applies to larger blocks. If a method first passes through an array once, at a cost of \(n\) operations, and then passes through it again, at a further cost of \(n\) operations, the total is \(n + n = 2n\) operations. Two separate passes over the same data cost twice one pass — they do not multiply.

14.2.3 Conditional Statements

An if else statement first evaluates its test condition, and then executes exactly one of the two branches. Its cost is therefore the cost of the test, plus the cost of whichever branch is taken.

if (a > b)
{
    max = a;
}
else
{
    max = b;
}

Here the test is constant time and each branch is a single assignment, so the whole statement is constant time.

But which branch is taken depends on the data, and the two branches need not cost the same. Suppose the if part is a single assignment while the else part contains a loop over the whole array. Then the same statement costs a constant on some inputs and \(n\) operations on others. When a single figure is wanted, the usual choice is the costlier branch, because that is what the method might have to do. Section 14.5 gives this practice its proper name and its proper limits.

An if else if chain works the same way. Each test is evaluated in turn until one succeeds, and then one block runs. A chain of a fixed number of constant-time tests and constant-time blocks is still constant time — a chain of four tests is not “four times slower in a way that matters”, because four does not grow with \(n\).

14.2.4 Loops

A loop is where growth enters. Its cost is the number of times the body is executed, multiplied by the cost of one execution of the body, plus the cost of the loop control itself.

for (int i = 0; i < n; i++)
{
    sum = sum + m[i];
}

The body is a constant-time statement, and it is executed once for each value of i from 0 to n - 1 — that is \(n\) times. The loop control performs a comparison and an increment on each pass, which adds a fixed number of operations per pass. The total is therefore some constant multiple of \(n\): the work grows in direct proportion to the input size. Double the array and you double the work.

The same reasoning applies to while and do while loops. What matters is not which keyword was used but how many times the body is entered.

Q. Does a do while loop that ends up running \(n\) times cost more than a while loop that runs \(n\) times?

A. No — both execute the body \(n\) times, so both cost a constant multiple of \(n\). The difference between them shows up only when the count could be zero: a while loop may skip its body entirely, whereas a do while always runs it at least once. That changes the answer, and sometimes the correctness, but not the growth pattern.

Two variations are worth checking against the rule.

If the control variable advances by two instead of one, the body runs about \(n/2\) times, so the count is halved but it still grows in direct proportion to \(n\). If the loop bound is a fixed number rather than n, as in for (int i = 1; i <= 100; i++), then the body runs one hundred times no matter how large the data is, and the loop is constant time. A loop is not automatically expensive; it is expensive when the number of passes is tied to \(n\).

14.2.5 Nested Loops

A nested loop is a loop placed inside the body of another loop. For every single pass of the outer loop, the inner loop runs through its whole range. The counts therefore multiply rather than add.

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        c = c + 1;
    }
}

The outer loop makes \(n\) passes. Each of those passes drives the inner loop through \(n\) passes of its own. The statement c = c + 1 is therefore executed \(n \times n = n^2\) times. At \(n = 10\) that is 100 executions; at \(n = 1000\) it is 1 000 000.

If the two loops run to different limits — the outer to \(m\) and the inner to \(n\) — the body runs \(m \times n\) times, and both quantities must be named when the cost is quoted.

adding the counts of nested loops instead of multiplying them What students write:

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= n; j++)
    {
        c = c + 1;
    }
}

What happens: the cost is reported as \(n + n = 2n\), on the reasoning that there are two loops of \(n\) passes each. At \(n = 1000\) this claims 2000 executions of c = c + 1, where the true figure is 1 000 000 — the estimate is off by a factor of five hundred. The fix: statements written one after another add their counts; a loop written inside another loop multiplies them. Ask how many times the inner body runs in total, not how many loops there are.

When the inner loop depends on the outer

Sorting methods rarely use two full-range loops. Far more often the inner loop starts where the outer one has reached, so that the range shrinks as the outer variable advances.

for (int i = 1; i <= n; i++)
{
    for (int j = i + 1; j <= n; j++)
    {
        c = c + 1;
    }
}

When i is 1 the inner loop runs \(n - 1\) times; when i is 2 it runs \(n - 2\) times; and so on down to zero when i reaches n. The total is

\[(n-1) + (n-2) + \cdots + 2 + 1 + 0 = \frac{n(n-1)}{2}\]

which multiplies out to \(\dfrac{n^2}{2} - \dfrac{n}{2}\). Fig. 14.2-1 shows why the sum comes out as half of a square: the pairs of values that actually occur fill exactly the region above the diagonal of an \(n \times n\) grid.

Diagram

Fig. 14.2-1 – square grid of n rows and n columns, rows labelled i = 1 to n from the top and columns labelled j = 1 to n from the left; every cell strictly above the main diagonal shaded, the diagonal cells and every cell below it left blank; the shaded region labelled “pairs for which the inner body runs” and a caption beneath reading “n(n−1)/2 cells shaded out of n² cells”

So this loop pattern does roughly half the work of the full nested pair, but it still grows as the square of the input size. Doubling \(n\) still multiplies the work by about four. Section 14.3 explains why the halving is not treated as a difference in kind.

The program below lets you check the formula rather than take it on trust.

counting the executions of a shrinking nested loop Problem: For a value of \(n\) fixed in the program, count how many times the innermost statement of the shrinking nested loop is executed, and display that count beside the value of \(n(n-1)/2\) for comparison.

class StepCount
{
    public static void main(String args[])
    {
        int n = 6;
        int count = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                count = count + 1;
            }
        }
        System.out.println("n = " + n);
        System.out.println("Inner body executed " + count + " times");
        System.out.println("n(n-1)/2 = " + (n * (n - 1) / 2));
    }
}

Sample output:

n = 6
Inner body executed 15 times
n(n-1)/2 = 15

Variable description:

[Table:] Table 14.4 – variable description for the program StepCount, listing each variable, its type and its purpose | Variable | Type | Purpose | |—|—|—| | n | int | The input size whose step count is being measured | | count | int | Counter incremented once for every execution of the inner body | | i | int | Control variable of the outer loop, running from 1 to n | | j | int | Control variable of the inner loop, running from i + 1 to n | [/Table]

Notes: The program does no useful work of its own — the inner statement exists purely to be counted. Written this way, it turns a formula that has just been derived on paper into something that can be verified at the keyboard for any n you choose.

14.2.6 Loops That Halve the Data

One more loop pattern appears constantly, and it behaves quite differently from the ones above. Instead of stepping through the data one item at a time, the loop discards half of what is left on every pass.

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

the halving loop above, traced with n = 64

Pass size at entry size after halving steps after the pass
1 64 32 1
2 32 16 2
3 16 8 3
4 8 4 4
5 4 2 5
6 2 1 6

Result: the loop ends with steps equal to 6. Sixty-four items were reduced to one in six passes, and \(2^6 = 64\) — the trace shows that the number of passes is the number of times \(n\) must be halved to reach 1.

That relationship can be written down directly. After \(k\) passes the remaining size is \(n/2^k\), and the loop stops when this reaches 1:

\[\frac{n}{2^k} = 1 \quad \Rightarrow \quad n = 2^k \quad \Rightarrow \quad k = \log_2 n\]

So the loop makes about \(\log_2 n\) passes. This is an extraordinarily slow-growing quantity. Doubling the data adds one extra pass, not twice as many passes. An array of a thousand items is exhausted in ten passes, a million in twenty, a thousand million in thirty.

Two honest qualifications. First, the derivation assumed \(n\) was an exact power of two; when it is not, the integer division rounds down and the count is the same figure rounded, never differing from \(\log_2 n\) by more than one pass. Second, this pattern only arises when the method genuinely discards half the remaining data on each pass. Halving is not available for free — the data usually has to be arranged in a particular way first, as section 14.6 will show.

A loop that multiplies its control variable by two on each pass, rather than dividing, behaves identically: for (int i = 1; i <= n; i = i * 2) also makes about \(\log_2 n\) passes, because it too crosses the range in doublings.

The counting rules together

Everything in this section reduces to five rules, collected here for reference.

Table 14.5 – how each construct contributes to the step count, with the rule applied to each

Construct Rule Resulting count
A simple statement Fixed work, independent of \(n\) Constant
Statements one after another Add the counts Sum of the parts
if else or if else if Test, plus the branch actually taken Cost of the costlier branch, when one figure is wanted
A loop tied to \(n\) Passes × cost of one pass Proportional to \(n\) for a simple body
A loop inside a loop Multiply the counts \(n^2\) for two full-range loops, \(n(n-1)/2\) when the inner range shrinks
A loop that halves the data Count the halvings About \(\log_2 n\)

Applying these to a whole method gives a formula such as \(3n^2 + 50n + 200\). That formula is more detail than anyone needs, and the next section explains which part of it survives — and why discarding the rest loses nothing that matters.

Copy StepCount and change the inner loop’s starting value from i + 1 to 1, leaving everything else alone. Predict the printed count for n = 6 before you run it, then run it and check. Explain in one line why the second printed line no longer agrees with the third.

14.3 The Dominant Term and the Role of Constants

Counting a whole method the way section 14.2 counts it produces something like

\[3n^2 + 50n + 200\]

Every part of that expression is honest — the \(n^2\) came from a nested loop, the \(50n\) from a single loop with a heavy body, the 200 from the setting up and finishing off. And almost none of it is useful.

The reason is that the expression answers a question nobody asked. Nobody needs to know the exact step count of a method at \(n = 37\). What is needed is the shape of its growth: what happens to the cost when the data gets larger. For that question, most of the expression is noise.

14.3.1 Identifying the Dominant Term

Work out what each of the three terms actually contributes as \(n\) increases.

Table 14.6 – value of each term of 3n² + 50n + 200 at five input sizes, with the share of the total contributed by the n² term

n \(3n^2\) \(50n\) 200 Total Share from \(3n^2\)
1 3 50 200 253 1.2%
10 300 500 200 1 000 30.0%
100 30 000 5 000 200 35 200 85.2%
1 000 3 000 000 50 000 200 3 050 200 98.4%
10 000 300 000 000 500 000 200 300 500 200 99.8%

Read the last column downwards. At \(n = 1\) the squared term is almost irrelevant and the constant 200 is doing most of the work. By \(n = 100\) the squared term accounts for over four-fifths of the cost. By \(n = 10\,000\) everything else together contributes less than a fifth of one per cent. The other terms have not disappeared; they have simply been left behind.

This happens for a reason that has nothing to do with the particular numbers chosen. Multiply \(n\) by ten and the constant term does not change at all, the linear term becomes ten times larger, and the squared term becomes a hundred times larger. Each round of growth widens the gap, and the widening never stops. Whichever term grows fastest will eventually account for as much of the total as you please.

That term has a name.

NoteDefinition

The dominant term of a step-count expression is the term that grows fastest as the input size \(n\) increases. For large enough \(n\) it accounts for almost the whole cost, and the remaining terms may be dropped without changing the description of how the cost grows.

The dominant term is chosen by rate of growth, not by size at any one input. In \(3n^2 + 50n + 200\) the dominant term is \(3n^2\), even though at \(n = 1\) it is the smallest of the three.

choosing the dominant term by looking at one small value of n What students write:

for (int i = 1; i <= 50; i++)
{
    total = total + i * n;
}
for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= n; j++)
    {
        total = total + 1;
    }
}

What happens: the counting is done correctly — 50 passes for the first loop and \(n^2\) for the nested pair, giving \(50 + n^2\) — and then, because 50 is the larger number when \(n\) is 5, the method is described as costing about 50 steps. From \(n = 8\) onwards that description is already wrong, and at \(n = 1000\) it is wrong by a factor of twenty thousand. The fix: compare the terms by asking what each does when \(n\) is multiplied by ten. The fixed 50 stays 50; the \(n^2\) becomes a hundred times larger. The term that responds to growth is the dominant one, however small it looks at the input you happened to try.

Q. Which of \(1000n\) and \(n^2/1000\) grows faster, and does the answer depend on where you look?

A. \(n^2/1000\) grows faster, although you have to look a long way out to see it. The two are equal when \(n^2/1000 = 1000n\), that is at \(n = 1\,000\,000\); below that the squared expression is the smaller of the two and above it the larger, by an ever-widening margin. The constants decide where the crossing happens, never whether it happens.

14.3.2 Why Constants Are Dropped

Having reduced \(3n^2 + 50n + 200\) to \(3n^2\), the usual practice goes one step further and reduces it to \(n^2\). The multiplying constant is dropped as well. That deserves justification, because at first sight throwing away a factor of three looks careless.

The argument is the one from section 14.1.3. A constant multiplier is exactly what a change of machine, a change of compiler or a slightly different way of writing the same statements produces. Rewrite the loop body so that it does two additions instead of six and the count halves; run the program on a machine twice as quick and the time halves again. None of these changes the fact that doubling the data quadruples the work. The constant describes the circumstances; the growth pattern describes the method.

And a constant, however large, cannot save a method whose growth is worse. Suppose one method takes \(100n\) steps and another takes \(n^2\) steps.

Table 14.7 – step counts of a 100n method and an n² method at six input sizes

n \(100n\) steps \(n^2\) steps Which is fewer
10 1 000 100 \(n^2\) method
50 5 000 2 500 \(n^2\) method
100 10 000 10 000 equal
200 20 000 40 000 \(100n\) method
1 000 100 000 1 000 000 \(100n\) method
10 000 1 000 000 100 000 000 \(100n\) method

The factor of one hundred buys the second method an advantage up to \(n = 100\), and not one step beyond. Fig. 14.3-1 shows the two curves meeting at that point and separating for good afterwards. Replace the hundred by a thousand and the crossing moves out to \(n = 1000\); it does not go away.

Diagram

Fig. 14.3-1 – graph with input size n on the horizontal axis marked at 50, 100, 200 and 500, and number of steps on the vertical axis; a straight line through the origin labelled “100n” and an upward-bending curve labelled “n²”; the two meet at the point (100, 10 000), which is marked with a dot and a dashed vertical line down to the axis; the region left of the crossing labelled “n² method does less work”, the region right of it labelled “100n method does less work”

So the constant fixes only where the crossing lies, and the growth pattern fixes what happens after it. Since the interesting inputs are usually the large ones, it is the growth pattern that is reported.

Q3. If a method takes \(3n^2 + 50n + 200\) steps, why is only the \(n^2\) part reported as its cost?

A. Because the rest stops mattering. As \(n\) grows, the \(n^2\) term overwhelms the others — at \(n = 10\,000\) it is already more than 99% of the total — so the two smaller terms describe only what happens at input sizes too small to be a problem anyway. The multiplier 3 is dropped for a different reason: a constant factor is what a faster machine or a tidier loop body changes, so it describes the circumstances rather than the method. What is left, \(n^2\), is the part that says doubling the data quadruples the work, and that statement holds on every machine.

14.3.3 Where Constants Still Matter

Dropping constants is a deliberate simplification, and like every simplification it throws away something real. It is worth being clear about what.

If two methods have the same growth pattern, the constants are the only thing left to choose between them. A method costing \(n^2\) steps and one costing \(10n^2\) steps are described identically, yet on the same data the first finishes in a tenth of the time. Anyone actually deciding which to use must look past the growth pattern and count more carefully — or measure.

The simplification is also silent about small inputs. Below the crossing point, the method with the worse growth pattern is genuinely the faster one, and if the data never gets large, it is the better choice. This is not a hypothetical nicety: it is exactly why a method with a poor growth pattern but a very small constant, such as the insertion sort of section 14.7.3, is preferred for short lists.

Two kinds of change to a method are therefore worth telling apart:

  • Changes that alter the growth pattern — removing a nested loop, arranging the data so that half of it can be discarded on each pass, avoiding a repeated pass over the whole array. These change what the method is.

  • Changes that alter only the constant — moving a computation out of a loop body, replacing two array accesses by one, using a faster machine. These make the same method cheaper by a fixed factor.

The first kind is where the large gains are, and it is the kind this chapter is about. The second kind is real, and worth doing, but it cannot rescue a method that grows badly. If a program is too slow at a hundred thousand records, tightening the loop body will not help; a different method will.

A method’s step count works out to \(2n^3 + 500n^2 + 10\,000n\). Without a computer, write down its dominant term, and find the smallest value of \(n\) at which the \(n^3\) term alone exceeds the other two terms put together. State in one line what your answer says about testing this method only on small data.

14.4 Big O Notation

Section 14.3 left a working method: count the steps, keep the dominant term, drop the constants. What remains is a bare growth pattern — \(n\), or \(n^2\), or \(\log n\). All that is missing is a settled way of writing it down, so that two people reading the same statement understand the same thing.

That way of writing it is big O notation. The symbol was introduced in 1894 by Paul Bachmann for use in number theory, long before there was any machine whose running time needed describing; computer scientists adopted it much later because it says exactly what is wanted about an algorithm.

14.4.1 Writing and Reading Big O

A cost is written as the capital letter O followed by an expression in \(n\) inside brackets: \(O(n)\), \(O(n^2)\), \(O(\log n)\). The expression inside is the growth pattern, with the dominant term kept and all constants removed.

Reading it aloud, \(O(n^2)\) is “order \(n\) squared”. The phrase “on the order of” is the sense intended: the method’s cost rises like \(n^2\) rises.

big O notation Statement: An algorithm has complexity \(O(f(n))\) if, from some input size onwards, its step count is at most a constant multiple of \(f(n)\). In words: the cost of the method grows no faster than \(f(n)\) grows, once the input is large enough for the pattern to show. Why it holds: from the counting rules of section 14.2, a method’s exact step count is a sum of terms in \(n\). Section 14.3 showed that the fastest-growing term eventually accounts for almost the whole sum, and that the constant multiplying it reflects the machine and the coding rather than the method. Keeping only the dominant term and discarding the constant therefore preserves everything about how the cost grows and discards everything that does not. Used for: stating what an algorithm costs in a form that holds on every machine; comparing two algorithms for the same task; predicting what will happen at input sizes larger than any yet tested. Watch out: the phrase “from some input size onwards” is part of the claim, not decoration. Big O says nothing about small inputs, and nothing about two methods that share the same order — an \(O(n^2)\) method and another \(O(n^2)\) method may still differ by a factor of ten in practice.

Applying the rules to the expression that opened section 14.3:

\[3n^2 + 50n + 200 \quad \longrightarrow \quad O(n^2)\]

A method whose cost does not grow with \(n\) at all is written \(O(1)\), read “order one” or “constant time”. The formula method of section 14.1.1 is \(O(1)\); the loop method is \(O(n)\), where \(n\) is the number to be summed.

Q. A method performs exactly 5 basic operations for every input, large or small. Is its complexity \(O(1)\) or \(O(5)\)?

A. \(O(1)\). The notation records growth, and 5 does not grow, so the constant is dropped like any other. \(O(1)\) does not mean “one step” — it means “a fixed number of steps, whatever the input size”. A method taking 5 steps and one taking 500 steps are both \(O(1)\).

Three conventions complete the notation.

Constants inside the brackets are removed, so \(O(2n)\) is written \(O(n)\) and \(O(n^2/2)\) is written \(O(n^2)\). Lower-order terms inside the brackets are removed, so \(O(n^2 + n)\) is written \(O(n^2)\). And the base of a logarithm is usually omitted, because changing the base only multiplies by a constant — \(\log_2 n\) and \(\log_{10} n\) differ by a fixed factor of about 3.32, which the notation discards anyway. Where the halving structure is the point, as in section 14.6.2, writing \(O(\log_2 n)\) makes the origin of the cost clearer, and both forms are in common use.

leaving constants and lower-order terms inside the brackets What students write:

for (int i = 0; i < n; i++)
{
    total = total + m[i];
}
for (int i = 0; i < n; i++)
{
    product = product * m[i];
}

What happens: the counting is right — two separate passes, so \(n + n = 2n\) operations — but the answer is then written as \(O(2n)\). It is not wrong arithmetic, it is a misuse of the notation: big O has already discarded constant factors by definition, so the 2 has no meaning inside the brackets. The fix: write \(O(n)\). Do the arithmetic in full while counting, then strip the constants and the lower-order terms at the last step, when converting the count into big O.

Every big O statement must say what \(n\) counts. “This method is \(O(n^2)\)” is incomplete; “this method is \(O(n^2)\), where \(n\) is the number of elements in the array” can be checked by someone else.

14.4.2 The Common Orders of Growth

Only a handful of growth patterns appear in ordinary programs. The order of growth of an algorithm is the pattern its cost follows as \(n\) increases, and knowing the standard ones by sight is most of the skill.

Table 14.8 – the common orders of growth, the name of each and the kind of method that produces it

Order Name Typically produced by
\(O(1)\) constant a fixed sequence of statements, with no loop tied to \(n\)
\(O(\log n)\) logarithmic a loop that halves the remaining data on each pass
\(O(n)\) linear a single loop that visits each item once
\(O(n \log n)\) — a pass over all the data combined with a halving structure
\(O(n^2)\) quadratic two nested loops, each tied to \(n\)
\(O(n^3)\) cubic three nested loops, each tied to \(n\)
\(O(2^n)\) exponential a method that doubles its work each time one item is added
\(O(n!)\) factorial a method that tries every arrangement of the data

The orders are listed from cheapest to costliest, and that ranking holds for every large enough \(n\):

\[O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)\]

The methods studied in this chapter occupy the first five of these positions. No method producing \(O(n \log n)\) is developed here; the order is listed because it sits between the linear and the quadratic and is met constantly in later work. The last two are included as a warning: they are what happens when a method examines every possible subset or every possible ordering of the data, and they are unusable at any input size a school office would recognise.

14.4.3 Comparing Orders as the Input Grows

The ranking above is easier to trust once the actual numbers are in front of you.

Table 14.9 – approximate number of steps demanded by each order at three input sizes

Order n = 10 n = 100 n = 1000
\(O(\log_2 n)\) about 3 about 7 about 10
\(O(n)\) 10 100 1 000
\(O(n \log_2 n)\) about 33 about 664 about 9 966
\(O(n^2)\) 100 10 000 1 000 000
\(O(n^3)\) 1 000 1 000 000 1 000 000 000
\(O(2^n)\) 1 024 about \(1.3 \times 10^{30}\) about \(1.1 \times 10^{301}\)

Read across the rows rather than down the columns. The logarithmic row barely moves: multiplying the data by a hundred adds seven steps. The linear row keeps pace with the data exactly. The quadratic row is a hundred times worse each time the data grows tenfold. And the exponential row leaves the page entirely — at \(n = 100\) its figure already exceeds the number of atoms usually estimated to be in the observable universe, so no improvement in hardware is of the slightest relevance to it.

Fig. 14.4-1 shows the same information as curves.

Diagram

Fig. 14.4-1 – single graph with input size n on the horizontal axis and number of steps on the vertical axis; five curves drawn from the same origin region and labelled at their right-hand ends: a nearly flat curve “O(log n)”, a straight line “O(n)”, a gently bending curve “O(n log n)”, a steeper curve “O(n²)” and a near-vertical curve “O(2ⁿ)”; the curves ordered from lowest to highest at the right edge of the graph

Another way to read the same table is to ask what one doubling of the data does to the cost. This is often the most useful single fact about an algorithm, because data tends to grow by doubling rather than by neat powers of ten.

Table 14.10 – effect on the step count when the input size is doubled

Order Effect of doubling n
\(O(1)\) no change
\(O(\log n)\) one extra step
\(O(n)\) twice as many steps
\(O(n^2)\) four times as many steps
\(O(n^3)\) eight times as many steps
\(O(2^n)\) the step count is squared

These six lines are worth carrying in your head. They convert an abstract order into a prediction: an \(O(n^2)\) method that takes one second on a file will take about four seconds when the file doubles, sixteen seconds when it doubles again, and something over four minutes after four doublings — while an \(O(n)\) method on the same sequence of files goes from one second to sixteen.

That is also the honest limit of what big O will tell you. It predicts the shape of the increase, not the starting figure. Whether the first file takes one second or one minute depends on constants the notation has thrown away, and the only way to find that out is to count more precisely or to measure.

An \(O(n^2)\) method processes a file of 5 000 records in 2 seconds. Using Table 14.10, work out on paper the time it would take on 10 000, 20 000 and 40 000 records. Then write one sentence saying what your figures assume about the machine, and why the answers would be useless if the method were \(O(2^n)\) instead.

14.5 Best, Average and Worst Case

So far each method has been given a single cost. That is only possible when the method does the same work on every input of a given size — as the summing loop of section 14.1.1 does, since it adds \(n\) numbers whatever those numbers are.

Most methods are not like that. They contain a decision, and the decision depends on the data. Two arrays of exactly the same length can send the same method along two quite different paths, and the step counts can differ enormously. A single figure will not describe both.

14.5.1 What the Three Cases Mean

Consider a method that checks whether an array is already arranged in ascending order. It compares each element with the one after it, and the moment it finds a pair out of order it can stop and answer false — there is no point examining the rest.

checking whether an array is in ascending order Input: an array m of \(n\) integers. Output: true if every element is less than or equal to the one after it, false otherwise. Method:

1. Repeat for i = 0 to n - 2:
2.     If m[i] > m[i + 1] then
3.         Return false
4. Return true

Why it works: an array is in ascending order exactly when no adjacent pair is out of order. Step 3 reports failure on the first such pair found; if the loop finishes without finding one, no pair anywhere is out of order, so step 4 is entitled to report success. Cost: 1 comparison in the best case, \(n - 1\) comparisons in the worst case; between the two on other inputs, with \(n\) the number of elements in the array.

checking whether an array is in ascending order Problem: Given an array of integers, report whether its elements are arranged in ascending order. Test the method on one array that is out of order and one that is in order.

class OrderCheck
{
    static boolean isSorted(int m[])
    {
        for (int i = 0; i < m.length - 1; i++)
        {
            if (m[i] > m[i + 1])
            {
                return false;
            }
        }
        return true;
    }

    public static void main(String args[])
    {
        int p[] = {90, 12, 25, 40, 63};
        int q[] = {12, 25, 40, 63, 90};
        System.out.println("First array sorted  : " + isSorted(p));
        System.out.println("Second array sorted : " + isSorted(q));
    }
}

Sample output:

First array sorted  : false
Second array sorted : true

Variable description:

[Table:] Table 14.11 – variable description for the program OrderCheck, listing each variable, its type and its purpose | Variable | Type | Purpose | |—|—|—| | m | int[] | Formal argument of isSorted(), the array being examined | | i | int | Loop control variable, indexing the first element of each adjacent pair | | p | int[] | Test array whose first two elements are already out of order | | q | int[] | Test array whose elements are in ascending order | [/Table]

Notes: The loop runs only to m.length - 2, because the comparison looks at m[i + 1] and must not read past the end of the array. The return false inside the loop is what makes the cost of this method depend on the data — without it, every input would cost the same.

Now count what happened on each of the two test arrays, both of which have five elements.

On p, the very first comparison is 90 against 12. That pair is out of order, so the method returns immediately. One comparison, and the size of the array made no difference at all — the same would have happened with five thousand elements.

On q, no pair is ever out of order, so the loop runs to the end: four comparisons for five elements, and \(n - 1\) comparisons in general.

Same method, same input size, one comparison against four. This is why complexity is quoted in three cases — the best case complexity, the worst case complexity and the average case complexity.

NoteDefinition

The best case complexity of an algorithm is the smallest number of steps it takes over all inputs of size \(n\) — the cost on the input that suits it most.

NoteDefinition

The worst case complexity of an algorithm is the largest number of steps it takes over all inputs of size \(n\) — the cost on the input that suits it least.

NoteDefinition

The average case complexity of an algorithm is the number of steps it takes averaged over all inputs of size \(n\), calculated under a stated assumption about how likely each input is.

For isSorted(), the best case is a single comparison, which is \(O(1)\); the worst case is \(n - 1\) comparisons, which is \(O(n)\), where \(n\) is the number of elements. Fig. 14.5-1 shows the general picture: for each input size, many different inputs are possible, each with its own step count, and the three cases pick out the bottom, the middle and the top of that spread.

Diagram

Fig. 14.5-1 – graph with input size n on the horizontal axis and number of steps on the vertical axis; at each of five input sizes a vertical scatter of dots representing different inputs of that size; three curves drawn through the scatter and labelled at their right-hand ends — “worst case” through the highest dot at each size, “average case” through the middle of the dots, “best case” through the lowest dot at each size

The average case is the awkward one, and it is worth being precise about why. To average, you must first say how likely each input is, and that assumption is a claim about the world, not about the algorithm. If the arrays handed to isSorted() are in genuinely random order, then a pair out of order turns up within the first few comparisons almost every time, and the average is close to the best case. If, on the other hand, the method is used to check files that are usually already in order, almost every call runs to the end and the average is close to the worst case. The algorithm has not changed. Only the assumption has.

treating the three cases as three input sizes What students write:

int r[] = {5, 2, 9};
int s[] = {5, 2, 9, 14, 20, 31, 47, 58};

What happens: the shorter array is described as the best case for isSorted() and the longer one as the worst case, on the reasoning that less data means less work. But r is out of order at its first pair and costs one comparison, while s is in order throughout and costs seven — the larger array is being called the worst case for entirely the wrong reason, and the description collapses as soon as a long array appears that fails immediately. The fix: the three cases compare different inputs of the same size. Fix \(n\) first, then ask which arrangement of \(n\) items makes the method do least work and which makes it do most. Growth with \(n\) is a separate question, answered by big O within each case.

14.5.2 Which Case to Quote

Three figures are more than most discussions need, and in practice one of them is usually singled out.

The worst case is the one normally quoted, for two reasons. It is a guarantee: whatever data arrives, the method will not do worse than this, and a promise that holds for every input is worth more than one that holds for some. It is also the case that decides whether a program is usable — a method that is quick on most files but unusable on one is a method that will fail on the day that file arrives.

The best case, quoted alone, is close to worthless. Every searching method finds the item immediately if the item happens to be first, so a best case of \(O(1)\) distinguishes nothing. It becomes interesting only in comparison — when one method’s best case is much better than another’s, or when a method can be arranged so that the common inputs fall near its best case.

The average case is the most realistic figure and the hardest to defend, because it rests on an assumption about the data that may not hold. Where it is quoted in this chapter, the assumption is stated alongside it.

Table 14.12 – Best case vs Average case vs Worst case

Feature Best case Average case Worst case
What it measures Fewest steps over all inputs of size \(n\) Steps averaged over all inputs of size \(n\) Most steps over all inputs of size \(n\)
Depends on an assumption about the data No Yes — how likely each input is No
What it promises The method can be this quick The method is usually about this quick The method is never slower than this
Difficulty of working it out Easiest Hardest Straightforward
Chief use Comparing two methods at their most favourable Estimating everyday running cost Guaranteeing behaviour on any input

One caution before moving on. The three cases are not three different algorithms, and a method is not “an \(O(n)\) method sometimes and an \(O(1)\) method at other times”. It is one method, whose cost is described by three separate statements, each of which must name the case it belongs to. Saying “linear search is \(O(1)\)” because it might find the item first is not a shortcut; it is a false claim about an algorithm that will often examine the whole array.

Write down, without running anything, an array of six integers on which isSorted() performs exactly three comparisons before returning false. Then key in OrderCheck, add your array as a third test case, and insert a counter that is incremented on every comparison so you can confirm the figure. Test also with an array of six equal values and say which case that input falls into.

14.6 Complexity of the Searching Algorithms

Searching is the plainest task in which two methods differ not by a little but by an entire order of growth. You met both methods in Class XI as ways of finding a value in an array. Here the question is different: what do they cost, and what does one of them demand in return for being so much cheaper.

Throughout this section \(n\) is the number of elements in the array, and the operation counted is the comparison of an array element with the value being looked for. Everything else the methods do — an assignment, an index calculation — happens a fixed number of times per comparison, so counting comparisons alone gives the correct growth pattern.

14.7 Complexity of the Sorting Techniques

Section 14.6 ended on a debt. Binary search is spectacularly cheap, but it demands sorted data, and this section works out what arranging that data costs.

Three sorting techniques are studied on this course — bubble sort, selection sort and insertion sort. All three rearrange the array in place, using only a fixed number of extra variables, so their space demands are identical and there is nothing to choose between them there. All three, in the worst case, cost \(O(n^2)\). Yet they are not the same method wearing three hats, and the differences between them are exactly what this section is about.

Throughout, \(n\) is the number of elements in the array. Two operations are worth counting separately: the comparison of two elements, and the exchange of two elements. They are not equally cheap — an exchange moves data about, a comparison only inspects it — and the three techniques differ far more in exchanges than in comparisons.

14.7.1 Bubble Sort

The idea is to compare each adjacent pair, exchanging them whenever they are out of order. One sweep along the array is enough to carry the largest value all the way to the last position, because as soon as the sweep reaches it, it wins every comparison from there on. A second sweep carries the second largest into place, and so on.

Fig. 14.7-1 shows one such sweep.

Diagram

Fig. 14.7-1 – a row of five boxes holding 38, 15, 47, 22, 9 with indices 0 to 4 beneath, drawn as four successive stages of one sweep; in each stage the adjacent pair being compared is ringed and an arrow labelled “exchange” or “no exchange” is placed beneath it; the final stage shows 15, 38, 22, 9, 47 with the last box shaded and labelled “largest value now in place”

bubble sort Input: an array m of \(n\) elements in any order. Output: the same array, rearranged in ascending order. Method:

1. Repeat for i = 0 to n - 2:
2.     Repeat for j = 0 to n - 2 - i:
3.         If m[j] > m[j + 1] then
4.             Exchange m[j] and m[j + 1]

Why it works: after the first sweep the largest element is at the last position and never moves again; after the second sweep the two largest occupy the last two positions, and so on. The upper limit of the inner loop shrinks by one on each pass because the tail of the array is already settled. After \(n-1\) sweeps only one element is left unplaced, and it must be the smallest, so the array is in order. Cost: \(\dfrac{n(n-1)}{2}\) comparisons in every case, and up to the same number of exchanges — that is \(O(n^2)\) for best, average and worst case, with \(n\) the number of elements.

bubble sort on a list of marks Problem: An array holds the marks scored by five students, in no particular order. Rearrange the marks in ascending order using bubble sort and display the result.

class BubbleSort
{
    static void bubbleSort(int m[])
    {
        for (int i = 0; i < m.length - 1; i++)
        {
            for (int j = 0; j < m.length - 1 - i; j++)
            {
                if (m[j] > m[j + 1])
                {
                    int t = m[j];
                    m[j] = m[j + 1];
                    m[j + 1] = t;
                }
            }
        }
    }

    public static void main(String args[])
    {
        int marks[] = {38, 15, 47, 22, 9};
        bubbleSort(marks);
        System.out.print("Sorted marks:");
        for (int i = 0; i < marks.length; i++)
        {
            System.out.print(" " + marks[i]);
        }
        System.out.println();
    }
}

Sample output:

Sorted marks: 9 15 22 38 47

Variable description:

[Table:] Table 14.17 – variable description for the program BubbleSort, listing each variable, its type and its purpose | Variable | Type | Purpose | |—|—|—| | m | int[] | Formal argument of bubbleSort(), the array being rearranged | | i | int | Counts the sweeps; after sweep i the last i + 1 positions are settled | | j | int | Indexes the first element of the adjacent pair being compared | | t | int | Temporary store used while exchanging two elements | | marks | int[] | The list of marks supplied by main() | [/Table]

Notes: The array is passed to the method and modified in place, so main() sees the rearranged values without anything being returned. The inner loop stops at m.length - 1 - i for two reasons: the - 1 prevents m[j + 1] from reading past the end of the array, and the - i avoids re-examining the tail that earlier sweeps have already settled.

BubbleSort.bubbleSort() on the array {38, 15, 47, 22, 9}

Sweep (i) Comparisons made Exchanges made Array after the sweep
0 4 3 15, 38, 22, 9, 47
1 3 2 15, 22, 9, 38, 47
2 2 1 15, 9, 22, 38, 47
3 1 1 9, 15, 22, 38, 47

Result: the array is left as 9, 15, 22, 38, 47 after 10 comparisons and 7 exchanges. The trace shows the shrinking sweeps — 4, then 3, then 2, then 1 — which is the pattern that produces the cost.

bubble sort Here \(n\) is the number of elements and the operation counted is the comparison m[j] > m[j + 1]. The sweeps make \(n-1\), \(n-2\), …, 1 comparisons, totalling \(\frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2}\). The dominant term is \(n^2\), so the cost is \(O(n^2)\) — and since neither loop’s bounds depend on the data, this count is the same for every input, making the best case \(O(n^2)\) as well.

Q. If the array handed to bubbleSort() is already in ascending order, does the method do less work?

A. Not as written. Both loops run to fixed limits, so all \(\frac{n(n-1)}{2}\) comparisons are made whatever the data; only the exchanges are avoided. The method has no way of noticing that it is finished. That is a weakness of this version rather than of the technique, and it can be repaired — see the task at the end of this section.

letting the inner loop run to the end of the array What students write:

for (int j = 0; j < m.length; j++)
{
    if (m[j] > m[j + 1])
    {
        int t = m[j];
        m[j] = m[j + 1];
        m[j + 1] = t;
    }
}

What happens: the program compiles, then stops at run time with an ArrayIndexOutOfBoundsException. On the last pass j equals m.length - 1, and m[j + 1] refers to a position one past the last element, which does not exist. The fix: the loop must stop at m.length - 1 - i. Whenever a loop body reads m[j + 1], the bound on j has to be one lower than usual — the loop is indexing pairs, and there is one fewer pair than there are elements.

14.7.2 Selection Sort

Bubble sort moves elements towards their places gradually, one exchange at a time. Selection sort does the opposite: it works out where an element belongs first, and moves it exactly once.

The array is thought of as two parts — a sorted part at the front, empty to begin with, and an unsorted part behind it. Each pass finds the smallest element of the unsorted part and exchanges it into the position just after the sorted part, which then grows by one.

Diagram

Fig. 14.7-2 – a row of five boxes holding 64, 12, 45, 8, 31 with indices 0 to 4 beneath, drawn as four stages; in each stage a bracket labelled “sorted part” spans the leading cells and a bracket labelled “unsorted part” spans the rest, the smallest cell of the unsorted part is ringed and labelled “minimum”, and a double-headed arrow shows it being exchanged with the first cell of the unsorted part; the final stage shows 8, 12, 31, 45, 64 entirely under the “sorted part” bracket

selection sort Input: an array m of \(n\) elements in any order. Output: the same array, rearranged in ascending order. Method:

1. Repeat for i = 0 to n - 2:
2.     Set min = i
3.     Repeat for j = i + 1 to n - 1:
4.         If m[j] < m[min] then set min = j
5.     Exchange m[i] and m[min]

Why it works: step 4 leaves min holding the position of the smallest element in the part from i to the end, so step 5 places that smallest element at position i. Everything before i is already smaller than everything from i onwards, so once a position is filled it never needs changing. After \(n-1\) passes only the last position is left, and it must already hold the largest value. Cost: \(\dfrac{n(n-1)}{2}\) comparisons in every case, and exactly \(n-1\) exchanges — that is \(O(n^2)\) for best, average and worst case, with \(n\) the number of elements.

selection sort on a list of prices Problem: An array holds the prices, in rupees, of five items of stationery, in no particular order. Rearrange the prices in ascending order using selection sort and display the result.

class SelectionSort
{
    static void selectionSort(int m[])
    {
        for (int i = 0; i < m.length - 1; i++)
        {
            int min = i;
            for (int j = i + 1; j < m.length; j++)
            {
                if (m[j] < m[min])
                {
                    min = j;
                }
            }
            int t = m[i];
            m[i] = m[min];
            m[min] = t;
        }
    }

    public static void main(String args[])
    {
        int price[] = {64, 12, 45, 8, 31};
        selectionSort(price);
        System.out.print("Sorted prices:");
        for (int i = 0; i < price.length; i++)
        {
            System.out.print(" " + price[i]);
        }
        System.out.println();
    }
}

Sample output:

Sorted prices: 8 12 31 45 64

Variable description:

[Table:] Table 14.18 – variable description for the program SelectionSort, listing each variable, its type and its purpose | Variable | Type | Purpose | |—|—|—| | m | int[] | Formal argument of selectionSort(), the array being rearranged | | i | int | Position currently being filled; everything before it is already settled | | min | int | Index of the smallest element found so far in the unsorted part | | j | int | Scans the unsorted part looking for a smaller element | | t | int | Temporary store used while exchanging two elements | | price | int[] | The list of prices supplied by main() | [/Table]

Notes: The inner loop records a position, not a value, so that the exchange in step 5 knows where to fetch from. When the smallest element is already at position i, the exchange swaps that element with itself — harmless, and cheaper to allow than to test for.

SelectionSort.selectionSort() on the array {64, 12, 45, 8, 31}

Pass (i) Comparisons made min at the end of the scan Exchange performed Array after the pass
0 4 3 64 with 8 8, 12, 45, 64, 31
1 3 1 12 with itself 8, 12, 45, 64, 31
2 2 4 45 with 31 8, 12, 31, 64, 45
3 1 4 64 with 45 8, 12, 31, 45, 64

Result: the array is left as 8, 12, 31, 45, 64 after 10 comparisons and 4 exchanges. Compare this with the bubble sort trace: the same 10 comparisons, but 4 exchanges instead of 7 — and 4 is \(n-1\), which is the most this method can ever perform.

selection sort Here \(n\) is the number of elements and the operation counted is the comparison m[j] < m[min]. The scans examine \(n-1\), \(n-2\), …, 1 elements, totalling \(\frac{n(n-1)}{2}\) comparisons, so the cost is \(O(n^2)\) in every case. The exchanges are counted separately and come to exactly \(n-1\), which is \(O(n)\) — the one respect in which this technique is cheap.

14.7.3 Insertion Sort

The third technique is the one card players use without being taught it. Hold the cards already picked up in order; take the next card; slide it back past every card larger than itself until it reaches its place.

Here the front of the array is kept in order, and each remaining element in turn is lifted out and inserted into that ordered front, the larger elements shifting one place right to make room.

Diagram

Fig. 14.7-3 – a row of five boxes holding 5, 27, 34, 19, 11 with indices 0 to 4 beneath, showing one insertion in three stages; stage one has the cell holding 19 lifted above the row and labelled “value held in t”, stage two shows 34 and 27 each moved one place to the right with curved arrows labelled “shift right”, stage three shows 19 dropped into the vacated cell; a bracket over the leading cells in each stage is labelled “part already in order”

insertion sort Input: an array m of \(n\) elements in any order. Output: the same array, rearranged in ascending order. Method:

1. Repeat for i = 1 to n - 1:
2.     Set t = m[i] and set j = i - 1
3.     Repeat while j >= 0 and m[j] > t:
4.         Set m[j + 1] = m[j]
5.         Set j = j - 1
6.     Set m[j + 1] = t

Why it works: before pass i the elements from 0 to i-1 are in order among themselves. The loop at step 3 shifts right exactly those of them that are larger than t, leaving a gap at the correct place, and step 6 fills it. So after pass i the elements from 0 to i are in order, and after the last pass the whole array is. Cost: \(n-1\) comparisons in the best case, \(\dfrac{n(n-1)}{2}\) in the worst case — that is \(O(n)\) and \(O(n^2)\), with \(n\) the number of elements.

insertion sort on a list of parcel weights Problem: An array holds the weights, in kilograms, of five parcels, in no particular order. Rearrange the weights in ascending order using insertion sort and display the result.

class InsertionSort
{
    static void insertionSort(int m[])
    {
        for (int i = 1; i < m.length; i++)
        {
            int t = m[i];
            int j = i - 1;
            while (j >= 0 && m[j] > t)
            {
                m[j + 1] = m[j];
                j = j - 1;
            }
            m[j + 1] = t;
        }
    }

    public static void main(String args[])
    {
        int weight[] = {27, 5, 34, 19, 11};
        insertionSort(weight);
        System.out.print("Sorted weights:");
        for (int i = 0; i < weight.length; i++)
        {
            System.out.print(" " + weight[i]);
        }
        System.out.println();
    }
}

Sample output:

Sorted weights: 5 11 19 27 34

Variable description:

[Table:] Table 14.19 – variable description for the program InsertionSort, listing each variable, its type and its purpose | Variable | Type | Purpose | |—|—|—| | m | int[] | Formal argument of insertionSort(), the array being rearranged | | i | int | Index of the element being inserted into the ordered front part | | t | int | Holds the value lifted out, so that its cell may be overwritten | | j | int | Moves leftward through the ordered part, shifting larger values right | | weight | int[] | The list of weights supplied by main() | [/Table]

Notes: The outer loop starts at 1, not 0, because a single element is already in order by itself. The test j >= 0 && m[j] > t must be written in that order: if j has fallen to \(-1\), the first condition fails and Java does not evaluate the second, which would otherwise attempt to read m[-1].

InsertionSort.insertionSort() on the array {27, 5, 34, 19, 11}

Pass (i) Value in t Comparisons made Values shifted right Array after the pass
1 5 1 27 5, 27, 34, 19, 11
2 34 1 none 5, 27, 34, 19, 11
3 19 3 34, 27 5, 19, 27, 34, 11
4 11 4 34, 27, 19 5, 11, 19, 27, 34

Result: the array is left as 5, 11, 19, 27, 34 after 9 comparisons. Pass 2 is the interesting row: 34 was already larger than everything before it, so a single comparison settled it and nothing moved. That is the behaviour the next paragraph turns into a cost.

insertion sort Here \(n\) is the number of elements and the operation counted is the comparison m[j] > t. Each pass makes between 1 and \(i\) comparisons depending on how far back the value has to travel. If the array is already in ascending order, every pass stops at its first comparison, giving \(n-1\) comparisons in total and a best case of \(O(n)\). If the array is in exactly descending order, every pass travels the whole way back, giving \(1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2}\) comparisons and a worst case of \(O(n^2)\). On average an element travels about half the way, which halves the count but leaves the dominant term \(n^2\), so the average case is \(O(n^2)\).

14.7.4 Comparing the Three Sorting Techniques

Before comparing them with each other, it is worth seeing what \(O(n^2)\) means as an actual quantity of work, since all three techniques land there in the worst case.

Table 14.20 – number of comparisons given by n(n−1)/2 at four array sizes

Number of elements \(n\) Comparisons \(\dfrac{n(n-1)}{2}\)
10 45
100 4 950
1 000 499 500
10 000 49 995 000

Multiplying the data by ten multiplies the work by about a hundred. This is the arithmetic behind the story that opened the chapter: a program that sorts a class list in no time at all is doing about fifty million comparisons on a list of ten thousand, and about five thousand million on a list of a hundred thousand.

Within that shared order, the three techniques differ in ways that matter.

Table 14.21 – Bubble sort vs Selection sort vs Insertion sort

Feature Bubble sort Selection sort Insertion sort
Basic idea Exchange adjacent elements that are out of order Find the smallest of the rest and place it Insert each element into an ordered front part
Comparisons, worst case \(\dfrac{n(n-1)}{2}\) \(\dfrac{n(n-1)}{2}\) \(\dfrac{n(n-1)}{2}\)
Comparisons, best case \(\dfrac{n(n-1)}{2}\) as written here \(\dfrac{n(n-1)}{2}\) \(n-1\)
Best case complexity \(O(n^2)\) \(O(n^2)\) \(O(n)\)
Average and worst case complexity \(O(n^2)\) \(O(n^2)\) \(O(n^2)\)
Exchanges or shifts Up to \(\dfrac{n(n-1)}{2}\) exchanges Exactly \(n-1\) exchanges Up to \(\dfrac{n(n-1)}{2}\) shifts
Notices that the data is already in order No No Yes
Extra memory needed A fixed number of variables A fixed number of variables A fixed number of variables
Suited to Teaching the idea; small arrays Data where moving an element is expensive Small arrays, and data already nearly in order

Two entries in that table carry most of the weight.

Selection sort is the technique to reach for when the elements themselves are costly to move — large records rather than single integers — because it guarantees at most \(n-1\) exchanges however disordered the data is. Bubble sort, on the same data, may perform hundreds of times as many.

Insertion sort is the technique to reach for when the data is already close to being in order, which happens far more often in practice than a textbook example suggests — a register with a few late entries appended, a price list with three items changed. It is the only one of the three whose cost falls when the data is favourable.

Q5. Bubble sort, selection sort and insertion sort all need roughly \(n^2\) comparisons in the worst case. Is there any reason left to prefer one of them over another?

A. Yes, for two reasons that big O deliberately hides. First, the three do not agree on the best case: insertion sort costs only \(n-1\) comparisons on data already in order, which is \(O(n)\), while the other two make the full \(\frac{n(n-1)}{2}\) comparisons whatever they are given. Second, comparisons are not the only operation — selection sort performs at most \(n-1\) exchanges, where bubble sort may perform \(\frac{n(n-1)}{2}\), and when the items being moved are large that difference decides everything. Two methods of the same order can still be very different methods.

None of this rescues \(O(n^2)\) as such. All three techniques become unusable at input sizes that a linear or logarithmic method would handle without effort, and no amount of choosing between them changes that. Methods with a better order of growth for sorting do exist and are met in later study; the choice within this group is a choice about constants and about favourable data, made under a ceiling that none of the three can lift.

Add a boolean variable to bubbleSort() that is set to false at the start of each sweep and to true whenever an exchange is made, and end the outer loop early when a whole sweep passes with no exchange. Run the changed program on an array already in ascending order and count how many sweeps it now performs. State the new best case complexity, and say why the worst case is unaffected.

14.8 Analysing Some Other Standard Methods

Searching and sorting are the standard illustrations, but the counting rules of section 14.2 apply to any method at all. This section applies them to three more kinds of code you have already written: methods that work across a two-dimensional array, the elimination method for solving simultaneous equations, and methods that call themselves.

Each of the three brings out a point that the searching and sorting examples left aside.

14.8.1 Methods on Two-Dimensional Arrays

A method that visits every cell of a two-dimensional array needs two nested loops — one for the rows and one for the columns within a row.

row totals of a two-dimensional array of marks Problem: A table holds the marks of three students in four subjects, one student per row. Display the total marks obtained by each student.

class RowTotals
{
    public static void main(String args[])
    {
        int marks[][] = {{72, 65, 80, 91},
                         {58, 77, 63, 70},
                         {88, 90, 84, 79}};
        for (int i = 0; i < marks.length; i++)
        {
            int total = 0;
            for (int j = 0; j < marks[i].length; j++)
            {
                total = total + marks[i][j];
            }
            System.out.println("Total for row " + i + " = " + total);
        }
    }
}

Sample output:

Total for row 0 = 308
Total for row 1 = 268
Total for row 2 = 341

Variable description:

[Table:] Table 14.22 – variable description for the program RowTotals, listing each variable, its type and its purpose | Variable | Type | Purpose | |—|—|—| | marks | int[][] | The table of marks, one row per student and one column per subject | | i | int | Row index; selects the student whose total is being formed | | j | int | Column index; selects the subject within the current row | | total | int | Running total for the current row, reset at the start of each row | [/Table]

Notes: total is declared inside the outer loop so that it begins again at zero for every row. The inner bound is marks[i].length, the length of the current row, rather than a fixed number — this keeps the method correct if the table is later given a different number of columns.

Count the additions. The inner loop body runs once for every column of every row, so with \(r\) rows and \(c\) columns it runs \(r \times c\) times. Fig. 14.8-1 makes the count visible: every cell of the grid is entered exactly once.

Diagram

Fig. 14.8-1 – rectangular grid of 3 rows and 4 columns holding the marks 72, 65, 80, 91 / 58, 77, 63, 70 / 88, 90, 84, 79, with row indices 0 to 2 down the left and column indices 0 to 3 across the top; a dashed arrow snakes left to right along row 0, then along row 1, then along row 2, labelled “order in which cells are visited”; a note at the right reading “12 cells, 12 additions”

For a square table of \(n\) rows and \(n\) columns the count is \(n^2\), so the method is \(O(n^2)\) where \(n\) is the number of rows. That looks alarming beside the \(O(n)\) of linear search — until you notice what \(n\) counts. A square table of \(n\) rows holds \(n^2\) values, and the method reads each of them once. Measured against the amount of data present, it does the least work anyone could ask for.

This is the clearest possible warning about naming \(n\). The same method is \(O(n^2)\) when \(n\) is the number of rows and \(O(N)\) when \(N\) is the number of cells, and both statements are correct. A nested loop is not evidence of waste; a nested loop that passes over the same data many times is.

using the row count as the column bound What students write:

for (int j = 0; j < marks.length; j++)
{
    total = total + marks[i][j];
}

What happens: on a table of 3 rows and 4 columns, marks.length is 3, so the loop adds only the first three subjects of each row. The program runs to completion and prints 217, 198 and 262 — no error message, no exception, just wrong totals. Had the table been square, the bug would never have shown at all. The fix: use marks[i].length, the length of the row being processed. marks.length counts the rows; marks[i].length counts the cells in row i, and these are different quantities whenever the table is not square.

Multiplying two \(n \times n\) matrices raises the count further. Each of the \(n^2\) cells of the result is a sum of \(n\) products, so three nested loops are needed and the method is \(O(n^3)\). Doubling the size of the matrices multiplies the work by eight.

14.8.2 Solving a System of Linear Equations

The elimination method you use in mathematics for simultaneous equations is an algorithm like any other, and its cost can be counted in the same way.

To solve \(n\) equations in \(n\) unknowns, the coefficients are held in a table of \(n\) rows and \(n+1\) columns, the last column holding the constant terms. The method removes one unknown at a time.

solving n linear equations by elimination Input: a table a of \(n\) rows and \(n+1\) columns holding the coefficients and constant terms of \(n\) equations in \(n\) unknowns. Output: the values of the \(n\) unknowns. Method:

1. Repeat for k = 0 to n - 1:
2.     Repeat for each row i below row k:
3.         Compute the factor that will remove the kth unknown from row i
4.         Repeat for each column j from k to n:
5.             Subtract factor times a[k][j] from a[i][j]
6. Work back from the last row to the first, substituting the unknowns already found

Why it works: step 5 leaves row i with a zero in column k, so that unknown has been removed from that equation without changing its solution — subtracting a multiple of one equation from another is a legitimate step. After the loop at step 1, the last row contains one unknown only, and step 6 recovers the rest one at a time. Cost: about \(n^3\) operations for the elimination and about \(n^2\) for the back substitution — that is \(O(n^3)\), with \(n\) the number of unknowns.

The count comes straight from the three nested loops. The outer loop runs \(n\) times, once per unknown eliminated; for each of those, up to \(n\) rows must be adjusted; and adjusting a row means updating up to \(n+1\) coefficients. That gives roughly \(n \times n \times n = n^3\) arithmetic operations. The back substitution of step 6 needs only about \(n^2\) operations, and by the rule of section 14.3 the \(n^2\) is absorbed by the \(n^3\) that dominates it.

The practical reading of \(O(n^3)\) is the last row of Table 14.10: doubling the number of unknowns multiplies the work by eight. A system of 10 equations costs about a thousand operations and is instant. A system of 1000 equations — an ordinary size in engineering work — costs about a thousand million, which is a different kind of task altogether, and it is why so much effort goes into methods that exploit special structure in the coefficients.

14.8.3 The Cost of a Recursive Method

A recursive method contains no loop, so the counting rules of section 14.2 do not apply directly. The question to ask instead is: how many calls are made altogether, and what does each call cost on its own.

recursive factorial Problem: Compute the factorial of a number using a recursive method, and display the factorial of 6.

class FactorialCost
{
    static long factorial(int n)
    {
        if (n <= 1)
        {
            return 1;
        }
        return n * factorial(n - 1);
    }

    public static void main(String args[])
    {
        System.out.println("factorial(6) = " + factorial(6));
    }
}

Sample output:

factorial(6) = 720

Variable description:

[Table:] Table 14.23 – variable description for the program FactorialCost, listing each variable, its type and its purpose | Variable | Type | Purpose | |—|—|—| | n | int | Formal argument of factorial(); the number whose factorial is required | [/Table]

Notes: The return type is long because factorials grow very quickly and would overflow an int beyond 12. The test n <= 1 is the base case, the point at which the method stops calling itself; without it the calls would continue past zero and never end.

FactorialCost.factorial() called with n = 6

Call Value of n Base case reached Value returned
1 6 no \(6 \times 120 = 720\)
2 5 no \(5 \times 24 = 120\)
3 4 no \(4 \times 6 = 24\)
4 3 no \(3 \times 2 = 6\)
5 2 no \(2 \times 1 = 2\)
6 1 yes 1

Result: factorial(6) returns 720. Read the table downwards to follow the calls being made, and upwards to follow the values coming back — the sixth call returns first, and each earlier call multiplies its own n into the value it receives. Six calls were made for \(n = 6\).

recursive factorial Here \(n\) is the number whose factorial is wanted. The method calls itself once with the argument reduced by one, so there are \(n\) calls in all, and each performs one comparison and one multiplication. The dominant term is \(n\), so the time complexity is \(O(n)\). The space complexity is also \(O(n)\): every call that has not yet returned occupies memory, so at the deepest point \(n\) calls are held at once.

That second figure is the one worth attending to, because an iterative version of the same computation keeps a single running product and needs no extra memory at all. Fig. 14.8-2 shows the calls stacking up.

Diagram

Fig. 14.8-2 – four boxes stacked vertically and labelled from the top factorial(4), factorial(3), factorial(2), factorial(1); a downward arrow on the left labelled “calls made, each waiting for the one below”; an upward arrow on the right labelled “values returned: 1, 2, 6, 24”; a bracket beside the stack labelled “depth 4 — memory held at the deepest point”

Table 14.24 – Iteration vs Recursion, for the same computation

Feature Iterative version Recursive version
How repetition is obtained A loop The method calls itself
Time complexity for factorial \(O(n)\) \(O(n)\)
Extra memory used A fixed number of variables, \(O(1)\) One stored call per level of depth, \(O(n)\)
What ends the repetition The loop condition becoming false The base case being reached
Failure when it goes wrong The loop never ends The calls never end and the memory holding them runs out
Chief merit Cheap in memory Often much closer to the definition of the problem

Recursion, then, does not change the number of basic operations here — it changes where the cost is paid. The time is the same as the loop’s; the memory is not.

One caution completes the picture. Not every recursive method is \(O(n)\). The factorial method makes one call at each level, so the number of calls equals the depth. A method that calls itself twice at each level doubles the number of calls from one level to the next, giving about \(2^n\) calls in total — the exponential row of Table 14.9, and unusable for any but the smallest \(n\). When analysing a recursive method, count the calls; the depth alone is not the answer.

Rewrite factorial() as an iterative method using a for loop, keeping the same signature and return type, and check that it prints the same value for 6. Then find, by trying successive values, the largest n for which your version returns a correct answer, and explain in one line what limits it — noting that this limit has nothing to do with complexity.

14.9 Summary

What complexity measures

  1. An algorithm is a finite, ordered set of unambiguous steps that takes an input and produces the required output. Computational complexity is the study of what carrying out those steps costs, and of how that cost grows as the data grows.

  2. The input size, written \(n\), is the number that measures how much data the algorithm is given. Every statement of complexity is meaningless until it is said what \(n\) counts — the elements of an array, the characters of a string, the rows of a table.

  3. Time complexity is the number of basic operations performed, expressed as a function of \(n\). Space complexity is the memory required, expressed as a function of \(n\). The two are quoted separately and can be traded against each other.

  4. Complexity is obtained by counting operations, not by timing a run. A measured time belongs to one machine on one afternoon; a step count belongs to the algorithm, can be worked out by reading the code, and predicts behaviour at input sizes not yet tested.

  5. A faster machine divides the time per step by a fixed factor. It does not change the number of steps, so it cannot rescue a method whose step count grows badly.

Counting the constructs

  1. A simple statement runs in constant time: its operation count does not depend on \(n\). A method call costs whatever the method costs, not one operation.

  2. Statements written one after another add their counts. A conditional costs the test plus the branch actually taken, and where one figure is wanted the costlier branch is used.

  3. A loop costs the number of times its body is entered multiplied by the cost of one execution. A loop whose bound is a fixed number is constant time; a loop tied to \(n\) is proportional to \(n\).

  4. A loop inside a loop multiplies the counts. Two full-range nested loops execute the inner body \(n^2\) times; when the inner range starts where the outer has reached, the count is \(\dfrac{n(n-1)}{2}\), which is still governed by \(n^2\).

  5. A loop that halves the remaining data on each pass makes about \(\log_2 n\) passes, because \(n/2^k = 1\) gives \(k = \log_2 n\). Doubling the data adds one pass, not twice as many.

Dominant term, constants and big O notation

  1. The dominant term of a step-count expression is the term that grows fastest as \(n\) increases. For large enough \(n\) it accounts for almost the whole cost, so the remaining terms may be dropped. It is chosen by rate of growth, never by which term is largest at one particular input.

  2. The constant multiplying the dominant term is dropped as well, because a constant factor is what a change of machine, compiler or coding style produces. A constant fixes only where two growth curves cross, never whether they cross.

  3. Big O notation: an algorithm has complexity \(O(f(n))\) if, from some input size onwards, its step count is at most a constant multiple of \(f(n)\). The clause “from some input size onwards” is part of the claim — big O says nothing about small inputs.

  4. Writing the notation: constants and lower-order terms are removed from inside the brackets, so \(3n^2 + 50n + 200\) becomes \(O(n^2)\) and \(2n\) becomes \(O(n)\). A method whose cost does not grow with \(n\) is \(O(1)\), which means a fixed number of steps and not necessarily one step. The base of a logarithm is usually omitted, since changing it alters only a constant factor.

  5. The common orders of growth, from cheapest to costliest, are \(O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)\).

  6. Doubling the input leaves an \(O(1)\) cost unchanged, adds one step to \(O(\log n)\), doubles \(O(n)\), quadruples \(O(n^2)\), multiplies \(O(n^3)\) by eight and squares the step count of \(O(2^n)\).

  7. Constants still matter in two situations big O ignores: between two methods of the same order, where the constant is all that separates them, and below the crossing point, where the method with the worse order may genuinely be the faster.

Best, average and worst case

  1. The three cases compare different inputs of the same size, not different sizes. Best case is the fewest steps over all inputs of size \(n\), worst case the most, average case the mean taken under a stated assumption about how likely each input is.

  2. Worst case is usually quoted, because it is a guarantee that holds for every input. Best case alone distinguishes little. Average case is the most realistic and the least secure, since it rests on an assumption about the data that may not hold.

Costs of the standard methods

  1. Linear search needs no order in the data. It costs 1 comparison at best, \(n\) at worst and about \(\dfrac{n+1}{2}\) on average for a successful search with the value equally likely at any position — that is \(O(1)\), \(O(n)\) and \(O(n)\), with \(n\) the number of elements.

  2. Binary search requires the array to be sorted. Each comparison discards half the remaining range, so it costs about \(\log_2 n\) comparisons in the worst case, giving \(O(\log_2 n)\). On a million elements that is about twenty comparisons against a possible million for linear search. Applied to unsorted data it reports present values as absent.

  3. Sorting is what buys the right to use binary search, and the three techniques on this course all cost \(O(n^2)\) in the worst case. Sorting once to run a single search is a poor bargain; sorting once to serve many searches is a good one.

  4. Bubble sort exchanges adjacent elements that are out of order. It makes \(\dfrac{n(n-1)}{2}\) comparisons in every case, so best, average and worst are all \(O(n^2)\), and it may make as many exchanges as comparisons. Ending the sweeps early when a whole sweep passes without an exchange gives it a best case of \(O(n)\).

  5. Selection sort finds the smallest element of the unsorted part and places it. It makes \(\dfrac{n(n-1)}{2}\) comparisons in every case, so all three cases are \(O(n^2)\), but it performs exactly \(n-1\) exchanges, which makes it the choice when moving an element is expensive.

  6. Insertion sort inserts each element into an ordered front part. It costs \(n-1\) comparisons on data already in order, which is \(O(n)\), and \(\dfrac{n(n-1)}{2}\) on data in exactly descending order, which is \(O(n^2)\); the average case is \(O(n^2)\). It is the only one of the three whose cost falls when the data is favourable.

  7. All three sorting techniques rearrange the array in place and need only a fixed number of extra variables, so their space demands are identical.

Other methods analysed

  1. A method that visits every cell of a table of \(n\) rows and \(n\) columns is \(O(n^2)\) where \(n\) is the number of rows — yet it reads each of the \(n^2\) stored values exactly once, so it is doing the least work possible on that data. A nested loop is not evidence of waste; repeated passes over the same data are.

  2. Multiplying two \(n \times n\) matrices needs three nested loops and is \(O(n^3)\).

  3. Solving \(n\) linear equations in \(n\) unknowns by elimination costs about \(n^3\) operations for the elimination and about \(n^2\) for the back substitution, so the method is \(O(n^3)\), with \(n\) the number of unknowns.

  4. For a recursive method, the count to make is the number of calls and the cost of each. Recursive factorial makes \(n\) calls each doing constant work, so it is \(O(n)\) in time; it is also \(O(n)\) in space, because every call not yet returned is held in memory, where an iterative version needs only \(O(1)\). A method that calls itself twice at each level makes about \(2^n\) calls and is unusable except at the smallest sizes.

14.10 Key Terms

  1. Algorithm — a finite, ordered set of unambiguous steps that takes an input and produces the required output.

  2. Average case complexity — the number of steps an algorithm takes averaged over all inputs of size \(n\), calculated under a stated assumption about how likely each input is.

  3. Base case — the condition in a recursive method under which it returns a value directly instead of calling itself, so that the chain of calls comes to an end.

  4. Basic operation — a single elementary action performed in a fixed amount of time, such as one comparison, one assignment, one arithmetic operation or one array access.

  5. Best case complexity — the smallest number of steps an algorithm takes over all inputs of size \(n\).

  6. Big O notation — a way of stating an algorithm’s cost: it has complexity \(O(f(n))\) if, from some input size onwards, its step count is at most a constant multiple of \(f(n)\).

  7. Binary search — a searching method for data already in sorted order, which compares the value sought with the middle element and discards half the remaining range at each step.

  8. Bubble sort — a sorting technique that repeatedly sweeps the array, exchanging each adjacent pair found out of order, so that one element settles into its final position on every sweep.

  9. Comparison — in the analysis of searching and sorting, the operation of testing one element against another or against a sought value; the operation usually counted when the cost is quoted.

  10. Computational complexity — the study of what an algorithm costs to carry out, and of how that cost grows as the input grows.

  11. Constant time — the property of a statement or method whose number of basic operations does not depend on the input size; written \(O(1)\).

  12. Dominant term — the term of a step-count expression that grows fastest as \(n\) increases, and which alone is kept when the cost is reported.

  13. Exchange — the operation of swapping the values held in two positions of an array; counted separately from comparisons because moving data is the more expensive of the two.

  14. Input size — a single number, written \(n\), measuring how much data an algorithm is given; every statement of complexity must say what \(n\) counts.

  15. Insertion sort — a sorting technique that keeps the front of the array in order and inserts each remaining element into that ordered part, shifting larger elements one place to the right.

  16. Linear search — a searching method that examines the elements one after another from the beginning until the value is found or the data is exhausted; it requires no order in the data.

  17. Nested loop — a loop placed inside the body of another loop, so that the inner loop runs through its whole range on every pass of the outer one and the two counts multiply.

  18. Order of growth — the pattern an algorithm’s cost follows as the input size increases, such as constant, logarithmic, linear, quadratic, cubic or exponential.

  19. Selection sort — a sorting technique that finds the smallest element of the unsorted part of the array and exchanges it into the position at the front of that part.

  20. Space complexity — the amount of memory an algorithm requires, expressed as a function of the input size \(n\).

  21. Time complexity — the number of basic operations an algorithm performs, expressed as a function of the input size \(n\).

  22. Worst case complexity — the largest number of steps an algorithm takes over all inputs of size \(n\); the figure usually quoted, because it holds for every input.

14.11 Points to Ponder

  1. Big O deliberately discards constant factors. Suppose a program is rewritten so that it runs ten times slower on every input, while its order of growth is unchanged. Nothing in its big O description has altered — so what, exactly, is big O for, and what should be used to describe the change that did happen?

  2. Sorting an array costs \(O(n^2)\) with the techniques of this chapter, and it buys searches at \(O(\log_2 n)\) instead of \(O(n)\). How many searches must a list receive before the sorting has paid for itself? What does your answer depend on besides \(n\) — and what happens to it if the list is altered between searches?

  3. The worst case is quoted because it is a guarantee that holds for every input. Consider a method that is quick on every input anyone is ever likely to supply, and catastrophic on one contrived arrangement of the data. Is it honest to describe that method by its worst case? Is it safe not to?

  4. A method that visits every cell of an \(n \times n\) table is \(O(n^2)\) in the number of rows and \(O(N)\) in the number of cells, and both statements are correct. If two correct descriptions of the same method can sound so different, what does that ask of anyone who quotes a complexity — and how would you decide which \(n\) to choose?

  5. Recursive factorial and iterative factorial perform the same number of multiplications, but one holds \(n\) unfinished calls in memory and the other holds none. When is a method that is easier to read but heavier on memory the better method, and who should make that judgement — the person writing the program or the person who will maintain it?

  6. Counting steps is machine-independent, which is exactly why it is preferred to timing a run. Yet programmers still measure running times constantly. What can a measurement tell you that a step count cannot, and is there any question about an algorithm that both methods answer equally well?

14.12 Objective Questions

  1. The term of a step-count expression that grows fastest as the input size increases is called the: [1 mark]
  1. constant term
  2. dominant term
  3. leading index
  4. input size
  1. A loop that discards half of the remaining data on every pass makes about how many passes for an input of size n? [1 mark]
  1. \(n/2\)
  2. \(n\)
  3. \(\log_2 n\)
  4. \(n^2\)
  1. Which of the following can be applied only to data already arranged in sorted order? [1 mark]
  1. linear search
  2. binary search
  3. bubble sort
  4. insertion sort
  1. The number of exchanges performed by selection sort on an array of n elements is at most: [1 mark]
  1. 1
  2. \(n - 1\)
  3. \(\dfrac{n(n-1)}{2}\)
  4. \(n^2\)
  1. A method performs exactly 40 basic operations for every input, whatever its size. Its time complexity is: [1 mark]
  1. \(O(40)\)
  2. \(O(n)\)
  3. \(O(1)\)
  4. \(O(\log n)\)

  1. Fill in the blank: doubling the input size multiplies the step count of an \(O(n^2)\) method by ____________ . [1 mark]

  2. Fill in the blank: a statement of complexity is incomplete until it has been said what ____________ counts. [1 mark]

  3. State whether true or false: insertion sort makes the same number of comparisons whatever the arrangement of the data. [1 mark]

  4. State whether true or false: a computer twice as fast halves the number of steps an algorithm performs. [1 mark]

  5. Match each method in Column A with its worst case time complexity in Column B, where n is the number of elements or the number of rows as appropriate. [1 mark]

Column A Column B
a. linear search i. \(O(n^2)\)
b. binary search ii. \(O(n^3)\)
c. selection sort iii. \(O(n)\)
d. multiplication of two \(n \times n\) matrices iv. \(O(\log_2 n)\)
  1. Assertion (A): A method whose step count is \(2n^2 + 500n\) is described as \(O(n^2)\). Reason (R): In big O notation, constant factors and lower-order terms are discarded. Choose the appropriate option: [1 mark]
  1. Both Assertion (A) and Reason (R) are true and Reason (R) is the correct explanation of Assertion (A).
  2. Both Assertion (A) and Reason (R) are true but Reason (R) is not the correct explanation of Assertion (A).
  3. Assertion (A) is true but Reason (R) is false.
  4. Assertion (A) is false but Reason (R) is true.
  1. Assertion (A): Binary search may be applied to an array whose elements are in any order. Reason (R): Binary search discards half of the remaining range after each comparison. Choose the appropriate option: [1 mark]
  1. Both Assertion (A) and Reason (R) are true and Reason (R) is the correct explanation of Assertion (A).
  2. Both Assertion (A) and Reason (R) are true but Reason (R) is not the correct explanation of Assertion (A).
  3. Assertion (A) is true but Reason (R) is false.
  4. Assertion (A) is false but Reason (R) is true.

14.13 Check Your Concepts

  1. Define the input size of an algorithm, and state why a complexity claim is incomplete without it. [2 marks]

  2. Define constant time, and give one example of a statement that runs in constant time. [2 marks]

  3. State what is meant by the dominant term of a step-count expression, and name the dominant term of \(7n^3 + 200n^2 + 5000\). [2 marks]

  4. Differentiate between time complexity and space complexity, giving one example of a method for which the two behave differently. [3 marks]

  5. A method’s step count works out to \(4n^2 + 12n + 9\). Express its complexity in big O notation, and justify each simplification you make. [3 marks]

  6. Differentiate between best case and worst case complexity, using linear search as your example and stating the input that produces each. [3 marks]

  7. Explain, by counting the halvings, why binary search costs about \(\log_2 n\) comparisons in the worst case. State clearly what \(n\) counts. [4 marks]

  8. State the best case, average case and worst case complexity of insertion sort, and explain what arrangement of the data produces each. [4 marks]

  9. Explain why a computer ten times faster is of almost no help to a method of complexity \(O(2^n)\), while it materially helps a method of complexity \(O(n)\). [4 marks]

  10. Compare bubble sort and selection sort with respect to comparisons, exchanges, best case complexity and the kind of data each suits. State, with reasons, which of the two you would choose for arranging 500 records in which each record is large and expensive to move. [6 marks]

  11. A list of n names is searched repeatedly. Sorting it with the techniques of this chapter costs \(O(n^2)\); thereafter each lookup costs \(O(\log_2 n)\) by binary search, against \(O(n)\) by linear search on the unsorted list. Set out, with reasoning, the circumstances under which sorting the list first is worthwhile, and the circumstances under which it is not. [6 marks]

14.14 Output & Debugging

  1. Study the fragment and answer the questions that follow. [3 marks]
int n = 5;
int c = 0;
for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= i; j++)
    {
        c = c + 1;
    }
}
System.out.println(c);

(a) State the value printed. (b) Write an expression in n for the number of times the statement c = c + 1 is executed. (c) State the complexity of the fragment in big O notation.

  1. The fragment below is intended to display the largest value in the array, but it fails when run. [3 marks]
int m[] = {4, 9, 2, 7};
int max = m[0];
for (int i = 1; i <= m.length; i++)
{
    if (m[i] > max)
    {
        max = m[i];
    }
}
System.out.println(max);

(a) State what happens when the fragment is executed and name the fault. (b) Rewrite the line that is at fault. (c) State the complexity of the corrected fragment in terms of the number of elements.

  1. Study the fragment and answer the questions that follow. [3 marks]
int size = 100;
int count = 0;
while (size > 1)
{
    size = size / 2;
    count = count + 1;
}
System.out.println(count);

(a) State the value printed. (b) State the value held in size immediately before the loop ends. (c) Name the order of growth this loop illustrates, and say which searching method of this chapter depends on it.

  1. Study the method below and answer the questions that follow. [3 marks]
static int mystery(int m[], int k)
{
    int c = 0;
    for (int i = 0; i < m.length; i++)
    {
        if (m[i] < k)
        {
            c = c + 1;
        }
    }
    return c;
}

(a) State in one sentence what the method returns. (b) State the number of comparisons m[i] < k it performs on an array of n elements. (c) State whether its cost depends on the values stored in the array, giving a reason.

  1. The fragment below is intended to compute \(2^n\) but does not terminate. [3 marks]
int n = 10;
int i = 1;
int p = 1;
while (i <= n)
{
    p = p * 2;
}
System.out.println(p);

(a) Explain why the loop never ends. (b) Add the single statement needed to correct it, stating where it must be placed. (c) State the complexity of the corrected fragment in terms of n.

14.15 Programming Practice

  1. A shop keeps the number of units of each of its items in an integer array. Write a class with a method that searches the array for a given quantity using linear search, returning the index at which it is found or \(-1\) if it is absent, and counting the comparisons it makes. The main() method must test the search twice — once with a quantity stored in the last position of the array and once with a quantity that is not present at all — displaying the result and the comparison count each time. Submit: the algorithm in pseudocode, the complete class, a variable description table, and one line stating the worst case complexity of your method with what n counts. [6 marks]

  2. Write a class that arranges an integer array in ascending order using selection sort. The sorting method must count the comparisons and the exchanges it performs, and the program must display the sorted array together with both counts. Run the program on an array of eight values already in ascending order and again on the same eight values in descending order. Submit: the complete class, a variable description table, and a short note stating whether either count changed between the two runs and explaining why. [6 marks]

  3. A table of examination marks has \(r\) rows, one per student, and \(c\) columns, one per subject. Write a single method that accepts such a two-dimensional array and returns the highest mark stored anywhere in it. The method must not assume that the table is square, and must not use any sorting. Submit: the method alone, together with one line stating its complexity in terms of \(r\) and \(c\), and one line explaining why that figure cannot be improved upon for this task. [4 marks]