Algorithms · Lecture Notes
Chapter 1: Introduction
Everything a computer does rests on a list of steps that someone wrote down beforehand. That list is called an algorithm. Many algorithms can solve the same problem, and they can differ enormously in speed: one finishes in milliseconds on a million items, another needs years for the same job. These notes begin with what an algorithm is and which properties a good one has. They then show how running time is measured, not in seconds but in the number of operations as a function of input size. Short Java programs with constant, linear, square-root, cubic, factorial, and exponential running times are traced line by line. The last topic is Euclid's algorithm, one of the oldest algorithms we know.
Learning outcomes
- Algorithm
- State the definition and the properties of an algorithm (input, output, definiteness, finiteness, effectiveness, correctness); write an everyday task as an algorithm and show which property a given procedure fails.
- Analysis
- Express running time as a function T(n) of the input size n; count the operations of a short program line by line; read from a growth table how running time changes as n grows.
- Complexity examples
- Find, with justification, the complexity class of short programs (1, n, √n, n3, n!, 2n); explain how memoization reduces an exponential running time to a linear one.
- Euclid's algorithm
- Trace the computation of the GCD step by step; justify the algorithm's correctness and its O(log min(a, b)) running time; explain why the worst-case inputs are consecutive Fibonacci numbers.
1.1The concept of an algorithm
The word “algorithm” comes from the Latinized form of the name of al-Khwarizmi, a mathematician who lived in Baghdad in the 9th century. His book on calculating with Hindu numerals became known in Europe through a Latin translation that begins with the words “Dixit Algorizmi” (“Al-Khwarizmi says”). Over time the name came to denote any method for carrying out a particular calculation step by step. Today behind every problem a computer program solves there is an algorithm: a search engine ranking its results, a map finding the shortest route, a photograph being compressed.
1.1.1What is an algorithm?
A recipe, an assembly manual for a piece of furniture, and the method of long division by hand all share one structure. Each starts with something in hand: ingredients, parts, two numbers. Then come steps in a fixed order. When the steps are done, the desired result appears: a dish, a cupboard, a quotient and a remainder. An algorithm is this structure as computer science defines it, with precise rules.
An algorithm is a finite sequence of instructions, each precisely defined, for solving a problem or performing a task. It takes input data, performs operations on it, and produces an output.
Three parts of the definition stand out. The first is input and output: an algorithm takes something in and gives something back. The second is definiteness of the steps: each step can be understood in only one way. The third is finiteness: the steps do not go on forever. Each of the three is treated below as a separate property.
An algorithm need not be written in a programming language. It can be described in English sentences, numbered steps, a flowchart, or pseudocode. A program is the algorithm written in a particular language to run on a particular machine. The same algorithm can be written in Java, Python, or C; each version is a separate program, but all of them follow the same algorithm. This distinction is the basis of algorithm analysis: whether an algorithm is good or bad is decided independently of the language it is written in and the machine that runs it.
1.1.2Properties of an algorithm
Not every list of steps counts as an algorithm. Donald Knuth names five properties: input, output, definiteness, finiteness, and effectiveness. In practice a sixth is added, correctness. Table 1.1 lists the six with short explanations; each is then discussed in turn.
| Property | Meaning |
|---|---|
| Input | Zero or more values are supplied from outside. |
| Output | At least one result is produced, and it is related to the input. |
| Definiteness | Each step has exactly one meaning and leaves no room for interpretation. |
| Finiteness | For every input, it stops after a finite number of steps. |
| Effectiveness | Each step is a basic operation that can actually be carried out. |
| Correctness | For every valid input, it produces the correct output. |
Input. An algorithm receives values from outside, either before it starts or while it runs. The number of inputs may be zero. For example, the task “print the first 100 primes” takes no value from outside, yet it is a perfectly valid algorithm. In most algorithms, though, the input is the problem itself: the array to be sorted, the number to be found, the road network between two cities.
Output. An algorithm produces at least one result, and the result is related to the input. A list of steps that produces nothing is useless, however long it runs. The output need not be a value printed on the screen. A value returned by a method, a modified array, or a yes/no decision is also an output.
Definiteness. Each step is defined precisely and can be understood in only one way. “Add a little salt” may be enough for a person, but it is meaningless to a machine. An algorithm requires that everyone who reads a step does the same thing. This is why phrases such as “a little,” “enough,” or “a suitable value” do not belong in an algorithm.
Finiteness. For every input, an algorithm stops after a finite number of steps. A program whose loop never ends on some inputs is not an algorithm for those inputs. The most common way to lose finiteness is a loop condition that never becomes false. For example, a loop that subtracts 2 from a number on every round and stops when it reaches zero skips over zero for odd numbers and runs forever.
Effectiveness. Each step is basic enough to be carried out in finite time, with pencil and paper or on a machine. “Find the prime factors of the number” cannot be written as a single step, because it is a problem in its own right; it becomes part of an algorithm only after it is broken into more basic steps. “Try every real number one by one” can never be carried out, because there are uncountably many real numbers.
Correctness. For every valid input, an algorithm produces the correct output. Giving the right answer on a few examples is not enough; correctness must be shown for all valid inputs, which usually takes a proof. The correctness of Euclid's algorithm is shown by such a proof in the last section of these notes.
The following method is meant to find the number of digits of an integer: “1. Counter = 0. 2. As long as the number is greater than 0, divide it by 10 (integer division) and increase the counter by 1. 3. Print the counter.” Which properties does this method satisfy?
- Input and output: it takes an integer and prints a counter value. Both are present.
- Definiteness: each step has one meaning: assignment, comparison, integer division, increment.
- Effectiveness: all of these operations can be done in a single machine step.
- Finiteness: a positive number shrinks every time it is divided by 10 and eventually becomes 0. For example 4075 → 407 → 40 → 4 → 0; it stops after four divisions and the counter is 4. If the number is 0 or negative, the loop is never entered and the method stops at once.
- Correctness: for positive numbers the result is correct. But for 0 the output is 0, although the number 0 has one digit. For negative numbers the output is also 0. The method gives wrong results on these inputs. Either the set of inputs must be restricted to positive numbers or these cases must be handled separately.
The example also shows that correctness depends on the set of inputs. An algorithm must be correct “for every valid input,” and which inputs are valid is stated at the outset in the definition of the problem. If the problem definition stays vague, whether the algorithm is correct stays vague too.
1.1.3An everyday example: making tea
An easy way to make the idea of an algorithm concrete is to write down a familiar everyday task step by step. The input to making tea is water, tea leaves, and optionally sugar and milk; the output is a cup of tea. The algorithm in the slides has six steps:
- Boil the water.
- Pour the boiled water into the teapot.
- Add the tea leaves to the teapot.
- Wait for the tea to brew.
- Strain the brewed tea into a cup.
- Optionally add sugar and milk.
This short list shows three important qualities of an algorithm.
Order matters. An algorithm is an ordered list of steps. The position of some steps can change: if steps 2 and 3 swap places, that is, if the leaves go into the teapot first and the boiling water is added afterward, the result is the same. But steps 1 and 5 cannot swap. Tea cannot be strained before the water has boiled; there would be nothing to strain. When writing an algorithm, one thinks carefully about which step must come before which, that is, about the dependencies between steps.
Definiteness is tested separately for each reader. The step “wait for the tea to brew” is enough for a person; an experienced one looks at the color of the tea and decides. For a computer the step is ambiguous: how long should it wait? For a machine the step would have to read “wait 10 minutes.” This is exactly what definiteness demands: everyone who reads a step must be able to do the same thing without interpreting it.
Algorithms contain decisions. Step 6 carries a condition: “if sugar is wanted, add sugar; if milk is wanted, add milk.” The path the algorithm follows can depend on the input. In programming this corresponds to the if statement. Likewise a step such as “wait until the water boils” is a loop. Sequences of steps, decisions, and loops are the building blocks of every algorithm.
Counting a recipe in everyday language as an algorithm as it stands. Phrases such as “by eye,” “until it reaches the right consistency,” or “pick a suitable number” destroy definiteness. Whether a step is definite is tested by asking whether someone who knows nothing about it (or a machine) could do the same thing.
1.1.4From algorithm to code: computing an average
Finding the average of three numbers is a small, convenient example of the relationship between an algorithm and a program. The input is three numbers (Number1, Number2, Number3), and the output is their average. The algorithm has three steps:
- Sum = Number1 + Number2 + Number3
- Average = Sum / 3
- Print the value of Average.
Written in Python, the algorithm looks like this:
def average(a, b, c):
avg = (a + b + c) / 3
return avg
a = float(input("Enter the first number: "))
b = float(input("Enter the second number: "))
c = float(input("Enter the third number: "))
result = average(a, b, c)
print("Average of the numbers:", result)The same algorithm in Java is shown below. The code is written as the main method of a class; the Scanner class needs the line import java.util.Scanner; at the top of the file.
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("Enter the first number: ");
double a = in.nextDouble();
System.out.println("Enter the second number: ");
double b = in.nextDouble();
System.out.println("Enter the third number: ");
double c = in.nextDouble();
double avg = (a + b + c) / 3;
System.out.println("Average of the numbers: "
+ avg);
}The two programs look different. In Python the computation is separated into a function, and the inputs are read with input and converted with float. In Java everything is inside main, the inputs are read through a Scanner object with nextDouble(), and the type of each variable (double) is written out. But both programs follow the same three steps: add the three numbers, divide the sum by 3, print the result. For example, for inputs 4, 7, and 10 both programs print 7.0.
This observation shows that an algorithm is independent of the language. A program is the algorithm's counterpart in a particular language. To understand and analyze an algorithm it does not matter which language it is written in. In these notes the code is given in Java, but the idea behind each piece of code carries over unchanged to any other language.
Declaring the variables in Java as int and writing (a + b + c) / 3. When two integers are divided, Java discards the fractional part: for 4, 7, and 9 the result is 6 instead of 6.67. The algorithm is correct, but the choice of type in the program implements it wrongly. This is why the code in the slides uses double; when working with integers, writing / 3.0 is enough.
1.1.5Kinds of algorithms
Algorithms are grouped by the problem they solve or by the design idea they follow. This course covers basic algorithms from each of the groups below.
- Sorting algorithms put items into order. Insertion sort, merge sort, and quicksort are the best-known members of this group. Because sorted data speeds up searching and many other operations, sorting is one of the most studied problems in computer science.
- Searching algorithms find a particular item in a collection of data. Linear search examines the items one by one. Binary search halves the range at each step in a sorted array. A hash table computes the location of the item directly.
- Graph algorithms work on structures made of vertices and the edges that connect them. Dijkstra's algorithm finds the shortest path between two points. Minimum spanning tree algorithms connect all vertices at the least total cost. The Ford–Fulkerson method computes the maximum flow that can pass through a network.
- String and compression algorithms work with text. Searching for a word in a text, storing words in a tree called a trie, and shrinking a file (Huffman coding, gzip) belong to this group.
- Design techniques describe not a single problem but a general solution idea that applies to many problems. Divide and conquer (merge sort, binary search, fast exponentiation), dynamic programming, greedy algorithms, backtracking, and branch and bound are the main ones.
- Randomized and approximation algorithms offer two different routes for hard problems. A randomized algorithm makes random choices in some of its steps. An approximation algorithm, for problems where finding the best solution would take far too long, finds quickly a solution that is provably within a given ratio of the best.
These groups are not mutually exclusive. Merge sort is both a sorting algorithm and an example of the divide-and-conquer technique. Quicksort with a randomly chosen pivot is at the same time a randomized algorithm.
1.1.6Deterministic and randomized algorithms
Another way to classify algorithms is to ask whether they always follow the same path when given the same input.
A deterministic algorithm follows the same steps and produces the same output on every run with the same input. A randomized algorithm, in contrast, makes random choices in some of its steps; so on the same input, different runs may follow different paths.
An algorithm that finds the largest element of an array is deterministic: if the array is the same, so are the elements compared and the order of comparison. Quicksort with a random pivot, on the other hand, may split the array at different points on each run. In a sense this algorithm rolls dice. But the result does not change; the array is sorted correctly every time. Only the path followed, and therefore the running time, changes.
What randomness buys an algorithm is not obvious at first glance. If quicksort always picks the first element as the pivot, an already sorted array drives the algorithm into its slowest behavior. A random pivot removes the notion of a “bad input”: no input gives a bad result on every run, and the expected time stays equally short on every input. Some randomized algorithms gain a great deal of speed by accepting a very small probability of giving a wrong answer. All the algorithms in the rest of these notes are deterministic.
1.2Algorithm analysis
Finding an algorithm that solves a problem is only half the job. If several algorithms solve the same problem, one also has to decide which to choose. The tool for that decision is algorithm analysis. This section explains what analysis measures, why the measurement is made in operation counts rather than seconds, and how far apart different algorithms drift as n grows.
1.2.1Why analyze?
Algorithm analysis studies how much of its resources, such as processor time and memory, an algorithm uses as a function of input size. The time requirement is called time complexity, and the extra memory requirement is called space complexity.
A small example shows the value of analysis clearly. Suppose we search for a number in a sorted array of one million (106) elements. Linear search starts at the beginning of the array and examines the elements one by one. If the number is not in the array, or is at the very end, it makes one million comparisons. Binary search looks at the middle element and continues in the left half if the target is smaller and in the right half if it is larger. Because each comparison halves the range, it makes at most 20 comparisons, since one million is about 220. Figure 1.1 compares the two numbers on a logarithmic scale.
Both algorithms are correct; both find the number. The difference between them lies only in resource use, and it is a factor of fifty thousand. Analysis makes it possible to see such a difference in advance, without writing the program, just by looking at the algorithm's steps. Which algorithm to choose is often decided by this kind of comparison.
1.2.2Input size and the basic operation
The first way that comes to mind to measure how long an algorithm takes is to run the program and time it. But the measurement depends on many things: the speed of the processor, the programming language, the compiler, the other programs running at the same time. The same code may take 2 seconds on a laptop and 0.3 seconds on a server. These numbers tell us about the machine, not about the algorithm.
Algorithm analysis therefore does not measure time in seconds. Instead it counts the basic operations the algorithm performs. A basic operation is one that takes constant time on a machine: adding or comparing two numbers, accessing an array cell, assigning a value to a variable. The operation count does not change from machine to machine. A fast machine performs each operation in less time, but the number of operations stays the same.
The operation count does depend on the input. Summing an array of five elements takes less work than summing an array of a million. The operation count is therefore written as a function of a number that measures the size of the input.
The input size n is the number that measures the size of the problem: the number of elements in an array, the number of rows of a matrix, the number of vertices of a graph. The number of basic operations an algorithm performs on an input of size n is denoted T(n) and is called the algorithm's running time.
What counts as the input size is chosen according to the problem. For an algorithm that processes an array, the natural choice is the number of elements. For an algorithm that multiplies two n × n matrices, it is n. For an algorithm that takes a single number as input there are two options: the value of the number, or the number of digits needed to write it. The two options give very different results; we return to this distinction when we study primality testing.
Two inputs of the same size can also require different numbers of operations. Linear search finishes with one comparison if the target is in the first cell of the array; if it is not in the array at all, it makes n comparisons. In analysis one therefore often studies the worst case: the input that requires the most operations among all inputs of the same size. The worst case gives a guarantee. The algorithm never performs more operations than this on any input.
1.2.3Counting line by line: the sum of an array
To see how operations are counted, consider a short program that computes the sum of an array of n elements. Next to each line of the code in the slides is written how many times that line runs.
int sum = 0; // 1 time
for (int i = 0; i < n; i++) // n+1 comparisons
sum += a[i]; // n times
return sum; // 1 timeThe count is done line by line.
int sum = 0;runs once, before the loop: 1 operation.- The comparison
i < nin theforline is made once each time the loop is entered. While i is 0, 1, …, n − 1 the condition is true and the loop body runs; that makes n comparisons. When i = n the condition is tested once more, turns out false, and the loop ends. In all, n + 1 comparisons. sum += a[i];is the loop body and runs n times.return sum;runs once: 1 operation.
The sum of these counts gives the running time:
T(n) = 1 + (n + 1) + n + 1 = 2n + 3
For a = {4, 1, 3}, counting step by step (n = 3):
sum = 0: 1 operation.- i = 0:
0 < 3is true (1 comparison),sum = 4(1 operation). - i = 1:
1 < 3is true,sum = 5. - i = 2:
2 < 3is true,sum = 8. - i = 3:
3 < 3is false (1 comparison); the loop ends. return 8: 1 operation.- Total: 1 + 4 comparisons + 3 additions + 1 = 9 operations. The formula agrees: T(3) = 2 · 3 + 3 = 9.
In this count the i++ increments and the a[i] accesses were not counted as separate operations. Had they been, the result would have been a different expression such as 4n + 3. Which operations to count is a choice, and the choice changes the coefficients. But one thing does not change: the operation count is always a multiple of n plus a constant. If the array doubles in size, the work roughly doubles.
1.2.4Why do constants become irrelevant?
The numbers 2 and 3 in the expression 2n + 3 depend on the machine and on the way of counting. On one machine a comparison may be twice as slow as an addition; a compiler may merge two operations into one instruction. Knowing these constants exactly is both hard and not very useful. What matters is how fast T(n) grows as n grows.
For n = 10, 2n + 3 = 23, and the constant term 3 makes up about an eighth of the total. For n = 106, 2n + 3 = 2,000,003, and the contribution of the 3 drops to about one part in a million. For large n only the fastest-growing term decides. Its coefficient also becomes irrelevant, because the coefficient affects every n by the same factor: it doubles the time but does not change the shape of the growth.
This idea leads to classifying algorithms by their growth rates. The functions 2n + 3, 5n, and n/2 + 100 all grow in proportion to n. They are called linear and are written briefly as Θ(n). The Θ (theta) notation discards constant coefficients and lower-order terms and keeps only the growth rate. Similarly, the O(n) (big O) notation means “grows at most in proportion to n”; that is, it gives an upper bound. In these notes both notations are used in these intuitive senses. For T(n) = 2n + 3 one can write both T(n) = Θ(n) and T(n) = O(n).
What is the growth rate of T(n) = 5n2 + 100n log2 n + 7? Which term dominates, and when?
- The terms are 5n2, 100n log2 n, and 7. The constant 7 becomes irrelevant at once for large n.
- n = 100: 5n2 = 50,000, 100n log2 n ≈ 100 · 100 · 6.64 ≈ 66,439. At this point the second term is larger, because its coefficient is 20 times greater.
- n = 1000: 5n2 = 5,000,000, 100n log2 n ≈ 996,578. Now the first term is five times larger.
- The ratio of the two terms is 5n2 / (100n log2 n) = n / (20 log2 n), which grows without bound as n grows. A calculation shows that the first term is ahead for good from n = 144 on.
- Result: T(n) = Θ(n2). The growth rate is determined not by the term with the larger coefficient but by the term that increases fastest as n grows.
1.2.5The growth table
The running times of algorithms fall into a few familiar families of functions: constant (1), logarithmic (log n), square-root (√n), linear (n), linearithmic (n log n), quadratic (n2), cubic (n3), exponential (2n), and factorial (n!). The best way to see how these functions behave as n grows is to put their values side by side. Table 1.2 gives the growth table from the slides.
| f(n) | n = 10 | n = 100 | n = 1000 | n = 106 | time (n = 106) |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 ns |
| log2 n | 3.3 | 6.6 | 10.0 | 19.9 | 19.9 ns |
| √n | 3.2 | 10 | 31.6 | 1,000 | 1 µs |
| n | 10 | 100 | 1,000 | 1,000,000 | 1 ms |
| n log2 n | 33.2 | 664.4 | 9,966 | 2.0 · 107 | 19.9 ms |
| n2 | 100 | 10,000 | 1,000,000 | 1.0 · 1012 | 16.7 min |
| n3 | 1,000 | 1,000,000 | 1.0 · 109 | 1.0 · 1018 | ≈ 32 years |
| 2n | 1,024 | 1.3 · 1030 | ≈ 1.1 · 10301 | ≈ 10301030 | far longer than the age of the universe |
| n! | 3,628,800 | 9.3 · 10157 | ≈ 102567 | ≈ 105565708 | far longer than the age of the universe |
Reading the table row by row yields several important observations.
Constant and logarithmic growth hardly grow at all. When n increases from 10 to 106, a factor of a hundred thousand, log2 n rises only from 3.3 to 19.9. The logarithm answers the question “how many times must I halve n to get down to 1?” Halving a million twenty times brings it down to 1. The 20 comparisons of binary search come from this number.
The square root grows much more slowly than the linear function. For n = 106, √n is only 1000. Reducing an algorithm from n to √n cuts the work by a factor of a thousand on an input of a million.
n log n is very close to linear. For a million elements, n log2 n is about 2 · 107, only twenty times the linear time. On a machine that performs 109 operations per second this is 20 milliseconds. Efficient sorting algorithms belong to this class.
Even among polynomials there are huge gaps. On the same input of a million, n2 operations take 16.7 minutes and n3 operations take about 32 years. A quadratic algorithm causes no trouble on small inputs, but becomes unusable as the input grows.
Exponential and factorial growth exceed every limit. 2n reaches 1.3 · 1030 even at n = 100. At 109 operations per second that is about 4 · 1013 years, while the age of the universe is about 1.4 · 1010 years. n! is faster still: it reaches 3,628,800 at n = 10 and a number with 158 digits at n = 100. Algorithms in these two classes are usable only on very small inputs.
The ordering in the table is used constantly in the rest of the course:
1 < log n < √n < n < n log n < n2 < n3 < 2n < n!
Here the sign “<” means that for sufficiently large n the function on the left stays below the one on the right, and moreover that the ratio between them grows without bound. For small values of n the order can break down: at n = 10, √n ≈ 3.2 is smaller than log2 n ≈ 3.3. At n = 16 both equal 4, and from then on √n is always ahead.
1.2.6A faster computer or a better algorithm?
There are two ways to speed up a slow program: buy a faster computer or find a better algorithm. The growth table shows that the two have very different effects.
A faster computer performs each operation in less time. This amounts to shrinking the constant coefficient in T(n). A machine a thousand times faster speeds up every algorithm a thousand times, but it does not change the shape of the growth. A better algorithm, on the other hand, changes the growth rate. Using a sort that performs n log n operations instead of one that performs n2 on a million elements brings the time down from 16.7 minutes to 20 milliseconds. That is a gain of about fifty thousand, and it grows further as n grows.
The same comparison can be made the other way round: what is the largest input that can be solved in a given time? Table 1.3 gives the largest values of n that a computer performing 109 operations per second can handle in one second.
| f(n) | Condition | Largest n |
|---|---|---|
| n | n ≤ 109 | 109 |
| n log2 n | n log2 n ≤ 109 | ≈ 3.96 · 107 |
| n2 | n2 ≤ 109 | 31,622 |
| n3 | n3 ≤ 109 | 1000 |
| 2n | 229 ≈ 5.4 · 108 ≤ 109 < 230 | 29 |
| n! | 12! ≈ 4.8 · 108 ≤ 109 < 13! | 12 |
Now suppose the computer becomes a thousand times faster. For the linear algorithm the solvable input also grows a thousandfold. For the quadratic algorithm it grows only by a factor of √1000 ≈ 31.6, and for the cubic algorithm by a factor of 10. For the exponential algorithm, since 210 ≈ 1000, n grows by only 10: from 29 to 39. A machine a thousand times faster lets an exponential algorithm handle ten more elements. This is why in algorithm design the real gain comes not from hardware but from ideas that lower the growth rate.
Judging an algorithm's speed from a single measurement in seconds. The verdict “my program finished in 0.2 seconds, so it is fast” holds only for that machine and that input size. When the input grows tenfold, a linear algorithm takes 2 seconds and a cubic algorithm takes 200. Analysis looks not at seconds but at the operation count as a function of n and at how fast it grows.
1.3Complexity examples
Behind every row of the growth table there are real algorithms. This section examines a short Java program from each class. For each program the same question is asked: what is the input size n, which operation is counted, and how many times, as a function of n, is that operation performed? Most of the programs are traced line by line, with the intermediate values given in a table.
1.3.1Constant time: printing the first element
The fastest algorithms are those that perform the same number of operations however large the input is. A method that prints the first element of an array is of this kind.
void printFirst(int[] a) {
if (a.length > 0)
System.out.println("First element: "
+ a[0]);
else
System.out.println("Array is empty");
}The method first tests whether the array is empty with the condition a.length > 0. If the array is not empty, it accesses the cell a[0] and prints its value; if it is empty, it prints the message “Array is empty”. In Java the length of an array is stored in the array object; reading length does not require counting the elements. Accessing any cell of an array also takes a single step, because the address of the cell is computed directly from the starting address.
So whether the array has 10 elements or 10 million, the method performs one comparison, one array access, and one print. For example, called with {5, 8, 12, 4} it prints “First element: 5”, and called with an empty array it prints “Array is empty”. The operation count is independent of n: T(n) = O(1).
An algorithm whose running time is independent of the input size and bounded by a constant is called constant time and its running time is written O(1). An algorithm whose running time grows in direct proportion to n is called linear time: O(n).
O(1) does not mean “a single operation.” A method that performs three operations and a method that performs a thousand are both constant time if that number does not depend on n. What matters is that the operation count does not change when the input grows.
1.3.2Linear time: finding the largest element
To find the largest element of an unsorted array one must look at every element at least once. An element that is not looked at could be the largest. The findMax method in the slides does this in a single pass.
Integer findMax(int[] a) {
if (a.length == 0)
return null; // empty array
int max = a[0];
for (int x : a)
if (x > max)
max = x;
return max;
}The return type of the method is Integer, not int. The reason is the empty-array case: an empty array has no largest element, and the method reports this by returning null. The type int cannot hold null; Integer is an object reference and can.
If the array is not empty, the variable max is initialized with the first element. Then the loop for (int x : a) walks through all the elements of the array in order. This “for each” loop delivers the elements from beginning to end without using an index; the first element is part of the traversal too. Each element is compared with max. If the element is larger, max is updated. When the loop ends, max is the largest of all the elements seen so far; and since the loop traversed the whole array, it is the largest element of the array.
Table 1.4 shows the method running on the array {5, 8, 12, 4}; Figure 1.2 shows the same trace with the figure from the slides.
| Round | x | x > max? | max (end of round) |
|---|---|---|---|
| start | — | — | 5 |
| 1 | 5 | 5 > 5 false | 5 |
| 2 | 8 | 8 > 5 true | 8 |
| 3 | 12 | 12 > 8 true | 12 |
| 4 | 4 | 4 > 12 false | 12 |
findMax looks at each element once. The top row shows the elements of the array; the bottom row shows the value of max after that element has been examined. After 12 is found the value does not change.On the four-element array the method makes four comparisons and returns 12. In general, on an array of n elements exactly n comparisons are made; this number does not depend on the contents of the array. The number of updates does depend on the contents. If the array is in decreasing order ({9, 5, 3, 2}) there are no updates at all. If it is in increasing order ({2, 3, 5, 9}), every element is larger than the one before, so n − 1 updates are made. In both cases the total work is proportional to n: T(n) = Θ(n).
The extra memory the method uses consists of the variables max and x. These two variables suffice however large the array is. The space complexity is therefore O(1). The input array itself is not counted in the space; space complexity measures the memory the algorithm allocates in addition to the input.
Initializing max with 0. If all the numbers in the array are negative, for example {−7, −3, −9}, no element is greater than 0, so the method wrongly returns 0. The starting value must be an element of the array itself (a[0]). This is why the code in the slides first handles the empty array and then starts with a[0].
1.3.3Square-root time: primality testing
An integer greater than 1 that has no positive divisors other than 1 and itself is called a prime number. The numbers 2, 3, 5, 7, 11, 13 are prime. Numbers greater than 1 that are not prime are called composite numbers: 9 = 3 · 3, 91 = 7 · 13.
The most direct way to tell whether a number n is prime is to check whether any number from 2 to n − 1 divides n. This method performs n − 2 divisions; for 97 it needs 95. But most of these divisions are unnecessary. The following theorem says that the search can be ended much earlier.
If n > 1 is composite, then n has a divisor greater than 1 that is less than or equal to √n.
Proof. Since n is composite we can write n = a · b with 1 < a, b < n. If both factors were greater than √n, their product would exceed √n · √n = n. This contradicts a · b = n. So at least one of a and b is less than or equal to √n, and that factor is the required divisor. ∎
The contrapositive of the theorem says: if there is no divisor up to √n, then n is prime. For example, in 91 = 7 · 13 the smaller factor is 7, and 7 ≤ √91 ≈ 9.5. There is no need to look at the larger factor 13 at all; once 7 is found, we know the number is composite.
A second saving is possible. An even number greater than 2 cannot be prime, because it is divisible by 2. An odd number, on the other hand, is not divisible by any even number, since an even divisor would make the number even too. So we first check whether the number is even; for odd numbers we try only odd divisors. The isPrime method in the slides combines these two ideas.
boolean isPrime(int n) {
if (n <= 1)
return false;
else if (n == 2)
return true;
else if (n % 2 == 0)
return false;
int limit = (int) Math.sqrt(n) + 1;
for (int i = 3; i < limit; i += 2)
if (n % i == 0)
return false;
return true;
}The first three branches of the method separate out the special cases. Numbers 1 and below are not prime by definition. 2 is the only even prime. Even numbers greater than 2 are not prime. These three branches return a result without entering the loop.
For odd numbers, limit = (int) Math.sqrt(n) + 1 is computed. Math.sqrt returns the square root as a double; the (int) conversion discards the fractional part and leaves ⌊√n⌋. The loop condition i < limit means i ≤ ⌊√n⌋, so the integer part of √n is also tried. The loop starts at 3 and with i += 2 tries only odd numbers. If a divisor is found, the method returns false at once. If the loop ends without finding a divisor, the number is prime and the method returns true.
How many divisions are performed? The worst case is when the number is prime, because then the loop runs to the end. The loop advances from 3 to √n in steps of two. There are about √n / 2 odd numbers in this range. Dropping the constant coefficient 1/2 gives T(n) = O(√n). A few concrete values confirm this count:
- n = 97: ⌊√97⌋ = 9; the divisors tried are 3, 5, 7, 9: 4 divisions. Trying every number from 2 to 96 would have taken 95 divisions.
- n = 1,000,000,007 (prime): √n ≈ 31,622.8; the odd numbers tried are 3, 5, …, 31,621: 15,810 divisions. The simple method would have performed about a billion divisions.
If the number is composite, the loop usually ends much earlier. For 221, ⌊√221⌋ = 14 and limit = 15; 3, 5, 7, 9, 11 do not divide it, 13 does (221 = 13 · 17), and the method returns false after 6 divisions.
1.3.4Code trace: isPrime(97)
The trace slide in the presentation executes the call isPrime(97) line by line. Table 1.5 gives the variable values of this trace, and Figure 1.3 shows the initial and final states.
| Step | Line | limit | i | 97 % i | Explanation |
|---|---|---|---|---|---|
| 1 | 2, 4, 6 | — | — | — | 97 > 1, 97 ≠ 2, 97 is odd: all three checks pass |
| 2 | 8 | 10 | — | — | (int) √97 + 1 = 9 + 1 = 10 |
| 3 | 9, 10 | 10 | 3 | 1 | 3 does not divide |
| 4 | 9, 10 | 10 | 5 | 2 | 5 does not divide |
| 5 | 9, 10 | 10 | 7 | 6 | 7 does not divide |
| 6 | 9, 10 | 10 | 9 | 7 | 9 does not divide |
| 7 | 9 | 10 | 11 | — | 11 < 10 is false: the loop ends |
| 8 | 12 | 10 | 11 | — | return true: 97 is prime |
isPrime(97) trace. (a) limit = 10 has been computed; the dashed vertical line marks the bound, and the label √97 ≈ 9.85 shows the true square root. The gray boxes are even numbers and are never tried. (b) The loop has ended: the remainders for 3, 5, 7, and 9 (1, 2, 6, 7) are written in; none of them is 0.The notable point of the trace is the step i = 11. The increment i += 2 makes i equal to 11 after 9. Because the loop condition 11 < 10 is false, the body does not run; 11 is never tried. There is no need to try any odd number above 10 either. If 97 had a divisor greater than √97, then by Theorem 1.1 it would also have a small divisor. That small divisor would already have been tried.
Setting the loop bound as i < (int) Math.sqrt(n). Then ⌊√n⌋ itself is not tried. For perfect squares the only small divisor can be exactly √n: 9, 25, 49, 121 come out prime. The error is not limited to perfect squares either. For numbers such as 15 (⌊√15⌋ = 3) and 35 (⌊√35⌋ = 5) the small divisor equals exactly ⌊√n⌋ and is skipped too. Below 100,000 this faulty version gives a wrong result for 84 numbers. The + 1 in the slides puts the bound itself into the loop.
1.3.5Input size: the value of the number or its length?
In primality testing we took the value of the number n as the input size and found a running time of O(√n). At first sight this looks even better than linear time. But the size of a number in a computer is measured not by its value but by the number of bits it takes to write it. The number 1,000,000,007 has a value of a billion, but is written with only 30 bits.
Let the bit length of the number be b. Then n is about 2b, and
√n ≈ √(2b) = 2b/2
follows. So the number of divisions grows exponentially in the bit length. Adding one bit to the number doubles its value and multiplies the number of divisions by about √2 ≈ 1.41. For a 30-bit number, 15,810 divisions are easy. For a 1024-bit number of the kind used in cryptography, on the order of 2512 divisions are needed; this falls in the “far longer than the age of the universe” row of the growth table.
This observation shows that the input size must be chosen carefully in a complexity calculation. For an algorithm that processes an array, the number of elements is a natural measure. For algorithms that work with a single number, the two measures give very different results. Complexity theory always takes the input size to be the number of bits needed to write the input. Running times that are polynomial in the value but exponential in the bit length are called pseudo-polynomial time. This is why methods that test the primality of large numbers quickly rest on ideas entirely different from trial division.
1.3.6Cubic time: matrix multiplication
Matrix multiplication is a basic operation in many fields, from scientific computing to computer graphics and neural networks. For n × n matrices A = [aij] and B = [bij], each entry of the product C = A · B is defined by the formula
cij = Σk=1..n aik · bkj (i, j = 1, 2, …, n)
That is, cij is the sum of the products of corresponding entries of row i of A and column j of B. In the example from the slides,
| 1 | 2 | · | 5 | 6 | = | 19 | 22 |
| 3 | 4 | 7 | 8 | 43 | 50 |
For example, c11 = 1 · 5 + 2 · 7 = 19 and c21 = 3 · 5 + 4 · 7 = 43. This definition turns directly into three nested loops:
int[][] multiply(int[][] A, int[][] B) {
if (B.length == 0 || (A.length > 0 && A[0].length != B.length))
throw new IllegalArgumentException("dimensions");
int n = A.length, m = B[0].length, p = B.length;
int[][] result = new int[n][m];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
int sum = 0;
for (int k = 0; k < p; k++)
sum += A[i][k] * B[k][j];
result[i][j] = sum;
}
return result;
}The code is not limited to square matrices. n is the number of rows of A; m is the number of columns of B; and p is the number of rows of B, which must equal the number of columns of A. The method begins with this check: if B is empty or the dimensions do not match, an IllegalArgumentException is thrown; only after that is B[0] accessed. The result has size n × m. In Java the code indexes the matrix from 0; there is a shift relative to the indices starting from 1 in the formula, but the computation is the same.
The two outer loops visit each cell (i, j) of the result matrix once. For each cell, sum is reset, the innermost loop adds up p products, and the result is written to result[i][j]. The innermost line sum += A[i][k] * B[k][j] runs n · m · p times in all. For square matrices n = m = p, so this number is n3:
T(n) = n · n · n = n3 multiplications ⇒ T(n) = Θ(n3)
The reasoning in brief: the result has n2 entries, and each entry requires n multiplications. For n = 100 a million multiplications are performed, and for n = 200 eight million. Doubling n multiplies the time by eight; this is the signature of cubic growth. Because the result matrix holds n2 cells, the space complexity is Θ(n2).
This straightforward method is not the fastest way to multiply matrices. Strassen's algorithm, which works with the divide-and-conquer idea, does the same job with about n2.81 multiplications. But the straightforward method is both the easiest to understand and still very widely used in practice on small and medium-sized matrices.
1.3.7Code trace: multiplying 2 × 2 matrices
When multiply is called with the 2 × 2 matrices from the slides, n = m = p = 2 and the result is created as a 2 × 2 zero matrix. Table 1.6 gives the variable values after each multiplication.
| i | j | k | A[i][k] · B[k][j] | sum | multiplications | Cell written |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 · 5 = 5 | 5 | 1 | — |
| 0 | 0 | 1 | 2 · 7 = 14 | 19 | 2 | result[0][0] = 19 |
| 0 | 1 | 0 | 1 · 6 = 6 | 6 | 3 | — |
| 0 | 1 | 1 | 2 · 8 = 16 | 22 | 4 | result[0][1] = 22 |
| 1 | 0 | 0 | 3 · 5 = 15 | 15 | 5 | — |
| 1 | 0 | 1 | 4 · 7 = 28 | 43 | 6 | result[1][0] = 43 |
| 1 | 1 | 0 | 3 · 6 = 18 | 18 | 7 | — |
| 1 | 1 | 1 | 4 · 8 = 32 | 50 | 8 | result[1][1] = 50 |
At the end of the trace result = [[19, 22], [43, 50]] is returned, and exactly 8 = 23 multiplications have been performed. The pattern in the table also shows the general case: i and j choose each result cell once, and k takes n values for each choice. For 3 × 3 matrices the same count gives 33 = 27 multiplications.
Thinking that matrix multiplication takes n2 time. The result matrix has n2 entries, and each entry is written once; this gives the impression that the work is n2. But the computation of each entry is a separate loop of length n. The number of nested loops determines how many times the innermost operation runs: here three loops, n3 operations.
1.3.8Factorial time: all permutations
Each ordering of n items is called a permutation. The number of permutations of n distinct items is n! = n · (n − 1) · … · 2 · 1 (n factorial).
Why the number of permutations is n! becomes clear when the ordering is built position by position. Any of the n items can go in the first position. For the second position n − 1 choices remain, for the third n − 2, and so on. The last position is filled by the one remaining item. Multiplying the choices gives n!. For three items there are 3 · 2 · 1 = 6 permutations: 123, 132, 213, 231, 321, 312.
For some problems the most direct solution is to try every permutation one by one. For example, the order in which a traveler visits n cities with the shortest total distance can be found by trying all orders. The permute method in the slides prints all permutations of an array.
void permute(int[] a, int k) {
if (k == a.length) { // a permutation is ready
System.out.println(Arrays.toString(a));
return;
}
for (int i = k; i < a.length; i++) {
swap(a, k, i); // put a[i] at position k
permute(a, k + 1); // arrange the rest
swap(a, k, i); // restore
}
}The method is recursive, and the parameter k tells which position of the array is being filled. Positions 0 through k − 1 are settled; the elements from k to the end are not yet arranged.
- Base case: when
k == a.length, all positions are filled. The array is then a permutation and is printed. - Recursive step: the elements at positions
k,k + 1, …, up to the last are brought to positionkin turn. For this,swap(a, k, i)moves elementito positionk. Thenpermute(a, k + 1)fills the remaining positions in the same way. - Undo: after the recursive call returns, the second
swaprestores the array. So the next round of the loop starts with the original order of the elements after positionk.
The helper method swap used in the code exchanges the values at two positions of the array: int t = a[x]; a[x] = a[y]; a[y] = t;. Arrays.toString converts the array to text in the form [1, 2, 3] and comes from the java.util.Arrays class.
Tracing the call permute({1, 2, 3}, 0):
- k = 0, i = 0:
swap(0, 0)leaves the array unchanged: [1, 2, 3]. The call descends to k = 1.- k = 1, i = 1: the array stays [1, 2, 3]; at k = 2 there is only one choice, and at k = 3 [1, 2, 3] is printed.
- k = 1, i = 2:
swap(1, 2)→ [1, 3, 2]; [1, 3, 2] is printed. The undo swap returns the array to [1, 2, 3].
- k = 0, i = 1:
swap(0, 1)→ [2, 1, 3]. The same process prints [2, 1, 3] and [2, 3, 1]. The undo swap restores the array to [1, 2, 3]. - k = 0, i = 2:
swap(0, 2)→ [3, 2, 1]. This time [3, 2, 1] and [3, 1, 2] are printed. The last swap again returns the array to [1, 2, 3]. - Result: 6 lines are printed, and when the method returns the array is in its original state. The method is called 16 times in all: 1 (k = 0) + 3 (k = 1) + 6 (k = 2) + 6 (k = 3).
Note that the order of output is 123, 132, 213, 231, 321, 312. This is not lexicographic order: 312 and 321 are in reverse positions. The swap method generates each permutation once, but it does not preserve lexicographic order.
How many operations? The number of lines printed is exactly n!. On each line Arrays.toString converts n elements to text. The total work is therefore Θ(n · n!). The calls at the intermediate nodes do not change this: the number of calls is a constant multiple of n! (about e · n! ≈ 2.72 · n!). This class is briefly called the “O(n!) class.” Table 1.7 shows how fast the factorial grows.
| n | n! | Time at 109 permutations per second |
|---|---|---|
| 3 | 6 | instant |
| 5 | 120 | instant |
| 10 | 3,628,800 | about 3.6 ms |
| 15 | 1.3 · 1012 | about 22 minutes |
| 20 | 2.4 · 1018 | about 77 years |
The permutations of ten items are generated in the blink of an eye; those of twenty items take a human lifetime. Trying all permutations is therefore a method usable only on very small inputs. For larger inputs, techniques such as backtracking and branch and bound prune most of the search; or one looks for an entirely different algorithm that exploits the structure of the problem.
Forgetting the second swap call. Without the undo, the array continues in each round from the scrambled state the previous round left behind. For {1, 2, 3} the output becomes [1, 2, 3], [1, 3, 2], [3, 1, 2], [3, 2, 1], [1, 2, 3], [1, 3, 2]: 123 and 132 are printed twice, and 213 and 231 are never produced. Undoing the change a call made once the call returns is also the basic rule of backtracking algorithms.
1.3.9Exponential time: naive recursive Fibonacci
The Fibonacci sequence begins with 0 and 1; each following term is the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … The definition is written as follows:
F(0) = 0, F(1) = 1, F(n) = F(n − 1) + F(n − 2) (n ≥ 2)
This definition is recursive and can be turned directly into a Java method. The first method in the slides, fib, does this; the second method, fibMemo, is the subject of the next subsection.
long fib(int n) { // naive recursion
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
static final int N = 92; // largest n for long
long[] memo = new long[N + 1]; // 0: not computed
long fibMemo(int n) { // memoization
if (n <= 1) return n;
if (memo[n] == 0)
memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
return memo[n];
}The fib method is an exact copy of the definition. n ≤ 1 is the base case and returns the value of n: F(0) = 0, F(1) = 1. Otherwise the method calls itself twice and adds the results. The return type is long because Fibonacci numbers grow quickly: F(47) no longer fits in an int.
The code is short and correct, but very slow. The reason is clearly visible in the call tree in Figure 1.5. fib(5) calls fib(4) and fib(3). fib(4) in turn calls fib(3) again. So fib(3) is computed twice, separately, from scratch. The repetition grows further down: fib(2) is called three times and fib(1) five times.
fib(5): 15 calls. Green nodes are base cases (f1, f0). The left and right subtrees solve the same subproblems from scratch. (b) The call tree of fibMemo(5): 9 calls. Orange dashed nodes (f2, f3) take the result ready-made from the memo array; their subtrees are never expanded.How many calls are made? Let C(n) be the total number of calls made by fib(n). In the base cases there is only the call itself: C(0) = C(1) = 1. In the other cases the counts of the two subcalls are added to the call itself:
C(n) = 1 + C(n − 1) + C(n − 2)
This recurrence is very similar to the Fibonacci recurrence. Computing the values in order gives C(0..6) = 1, 1, 3, 5, 9, 15, 25. By induction one can show that C(n) = 2F(n + 1) − 1. For n = 5 that is 2 · 8 − 1 = 15, and for n = 30 it is 2 · 1,346,269 − 1 = 2,692,537 calls. fib(40) makes 331,160,281 calls; that means more than three hundred million method calls to find the 40th Fibonacci number.
Growth rate. Each call spawns at most two calls, and the depth of the tree is at most n. A binary tree of depth n can have at most 2n nodes. Hence T(n) = O(2n). The true growth is a little slower, because the right branches are shorter than the left ones. C(n) grows at the same rate as F(n), and F(n) is multiplied at each step by about the golden ratio φ = (1 + √5) / 2 ≈ 1.618. The exact class is Θ(φn) = Θ(1.618n). Although the base is 1.618 rather than 2, the growth is still exponential: when n increases by one, the time grows by about 62 percent, and when n increases by ten, it grows by more than a hundred and twenty times.
1.3.10Memoization: solving each subproblem once
The slowness of the naive Fibonacci code comes from solving the same subproblem again and again. When fib(30) is computed, F(2) is recomputed hundreds of thousands of times. Yet F(2) is the same value every time. If it were computed once and written down somewhere, every later request could read it from there.
Memoization is the technique of storing the results of subproblems computed in a recursive algorithm in a table and, when the same subproblem is requested again, returning the stored value without recomputing it.
The fibMemo method in the slides uses a long array called memo. Cell k of the array holds F(k). In Java all cells of a new long array start at 0. Here the value 0 is used to mean “not yet computed.” This choice is safe, because in the range without overflow (n ≤ 92) F(k) is never 0 for k ≥ 1; F(0) = 0 is handled separately in the base case. The constant N is the largest n to be computed, and the array is allocated with N + 1 cells. N = 92 is chosen because F(92) is the largest Fibonacci number that fits in a long; F(93) overflows. For larger n, BigInteger should be used.
The method first tests the base case. Then, if memo[n] == 0, that is, if F(n) has not been computed before, it computes it with two recursive calls and writes it into the array. In every case it returns the result from the array. In this way each F(k) is computed only once.
Tracing the call fibMemo(5) when the memo array is all zeros:
fibMemo(5)→memo[5] == 0; firstfibMemo(4)is called. In the same way the chain 4 → 3 → 2 descends.fibMemo(2)makes the callsfibMemo(1) = 1andfibMemo(0) = 0;memo[2] = 1is written.- Back in
fibMemo(3); the second call isfibMemo(1) = 1.memo[3] = 1 + 1 = 2. - Back in
fibMemo(4); the second call isfibMemo(2).memo[2]is now 1; the call returns 1 without computing anything.memo[4] = 2 + 1 = 3. - Back in
fibMemo(5); the second callfibMemo(3)returns 2 from memory.memo[5] = 3 + 2 = 5. - Result: F(5) = 5. A total of 9 calls were made:
f5, f4, f3, f2, f1, f0, f1, f2, f3. The last two are the calls that returned from memory.
How many calls? For n ≥ 1, fibMemo(n) makes exactly two subcalls for each k from 2 to n. The first computes F(k − 1). The second asks for F(k − 2); this call either returns from memory or is a base case. Adding the first call gives 2(n − 1) + 1 = 2n − 1 calls in all. For n = 5 that is 9, for n = 30 it is 59. Compared with the 2,692,537 calls of the naive method, the difference is a factor of about forty-five thousand. The running time drops to O(n).
This gain has a price: the memo array holds n + 1 cells. Moreover, since the recursion descends to depth n, the call stack also occupies O(n) space. Memoization spends memory to save time. This trade-off between time and memory is common in algorithm design. The same idea written bottom-up with a loop is the basis of dynamic programming.
Translating a recursive definition directly into code without checking whether the subproblems repeat. The naive fib gives the correct result, but in O(2n) time. If the call tree of a recursion shows several calls with the same argument, storing the results often brings the time down from exponential to polynomial.
1.4Euclid's algorithm
Euclid's algorithm is one of the oldest algorithms known. The Greek mathematician Euclid describes the method in his Elements, written around 300 BC. The algorithm has been in use for about two thousand three hundred years and still does useful work today in places ranging from cryptography to reducing fractions. Because it is short, has an easily proved correctness, and is surprisingly fast, it is also a very good vehicle for learning analysis.
1.4.1The GCD and Euclid's idea
The largest positive integer that divides two integers without remainder is called their greatest common divisor (GCD) and is written gcd(a, b). For example gcd(12, 18) = 6 and gcd(17, 5) = 1.
The most direct way to find the GCD is to start at min(a, b) and try every number downward. The first number that divides both is the GCD. In the worst case this method makes min(a, b) trials: O(min(a, b)). Another way is to factor both numbers into primes and multiply the common factors; but factoring large numbers is itself a hard problem.
Euclid's idea is to divide the larger number by the smaller and continue with the remainder. The basic identity is
gcd(a, b) = gcd(b, a mod b), gcd(a, 0) = a
Here a mod b is the remainder of dividing a by b. The algorithm is described in three steps:
- The larger number is divided by the smaller and the remainder is found.
- The operation is repeated with the pair (divisor, remainder) until the remainder is zero.
- When the remainder is zero, the last divisor is the GCD.
The identity turns directly into a recursive method:
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}b == 0 is the base case; gcd(a, 0) = a, because every number divides 0 and the largest number dividing a is a itself. Otherwise the method calls itself with (b, a % b). In Java the % operator gives the remainder.
The method also works when a < b. For example, in the call gcd(650, 1599), 650 % 1599 = 650, and the first call becomes gcd(1599, 650). The numbers swap themselves; the cost is just one extra division.
1.4.2Why is the algorithm correct?
Let a ≥ 0 and b > 0 be integers. The common divisors of a and b are the same as the common divisors of b and a mod b. Therefore gcd(a, b) = gcd(b, a mod b).
Proof. Divide a by b: a = q · b + r, where q is the quotient, r = a mod b is the remainder, and 0 ≤ r < b.
(1) Let d divide both a and b. Then d also divides q · b and hence the difference r = a − q · b. So every common divisor of a and b is also a common divisor of b and r.
(2) Conversely, let d divide both b and r. Then it also divides the sum a = q · b + r. So every common divisor of b and r is also a common divisor of a and b.
Since the two sets are equal, their largest elements are equal too. ∎
The theorem says that every recursive call preserves the GCD. Finiteness is also easy to show. In each call the second argument goes from b to a mod b, and a mod b < b. Since nonnegative integers cannot decrease forever, the second argument eventually becomes 0 and the base case is reached. The a returned in the base case is the correct GCD. So the algorithm both stops and gives the correct result.
1.4.3Code trace: gcd(1599, 650)
The trace example in the slides is gcd(1599, 650). Table 1.8 gives the division in each call.
| Call | a | b | Division | a % b |
|---|---|---|---|---|
| 1 | 1599 | 650 | 1599 = 2 · 650 + 299 | 299 |
| 2 | 650 | 299 | 650 = 2 · 299 + 52 | 52 |
| 3 | 299 | 52 | 299 = 5 · 52 + 39 | 39 |
| 4 | 52 | 39 | 52 = 1 · 39 + 13 | 13 |
| 5 | 39 | 13 | 39 = 3 · 13 + 0 | 0 |
| 6 | 13 | 0 | b == 0: return 13 | — |
After five divisions the remainder is 0, and the sixth call is the base case. The value 13 returns unchanged through all the calls; each call merely passes on the result of its subcall. The result is gcd(1599, 650) = 13. Factoring confirms this: 1599 = 3 · 13 · 41 and 650 = 2 · 52 · 13; the only common factor is 13.
The figures in the slides give a geometric interpretation of the algorithm. From a rectangle of size a × b, squares with side b are cut. As many squares as fit (q of them) are cut, leaving a strip of size b × r. The same operation is applied to this strip. When the strip is finally divided exactly into squares, the side of the last square is the GCD. Figure 1.6 shows three steps of this process.
The last observation also explains the meaning of the GCD. The squares with side 13 tile 39 × 13. These squares also tile 52 × 39, because both 52 and 39 are multiples of 13. The same reasoning works step by step backward, and in the end the 1599 × 650 rectangle too is tiled by 123 × 50 squares of size 13 × 13. This is the largest square that can tile this rectangle.
The recursive calls accumulate on the call stack. When the base case is reached, the stack holds six frames: from gcd(1599, 650) to gcd(13, 0). Since this depth is proportional to the number of divisions, the space complexity of the recursive version is of the same order as the number of divisions.
1.4.4Why is the algorithm fast?
gcd(1599, 650) finished in just five divisions. The trial method would have tried 638 numbers, from 650 down to 13. This difference is no accident. In Euclid's algorithm the numbers shrink very fast, and the following observation guarantees it.
If a ≥ b > 0, then a mod b < a / 2.
Proof. There are two cases. If b ≤ a / 2, then since the remainder is smaller than the divisor, a mod b < b ≤ a / 2. If b > a / 2, then b fits into a only once; the quotient is 1 and the remainder is a − b. Since b > a / 2, we get a − b < a / 2. In both cases the remainder is less than half of a. ∎
Consider two consecutive steps of the algorithm: (a, b) → (b, r) → (r, b mod r). After two steps, the place of the first number is taken by r = a mod b, and by the theorem r < a / 2. So every two steps the larger number at least halves. A number a can be halved at most log2 a times before it drops below 1. The number of divisions is therefore at most about 2 log2 min(a, b). After the first step the larger number of the pair is already at most min(a, b); this is why the smaller number appears in the bound. The running time is
T(a, b) = O(log min(a, b))
Compared with the O(min(a, b)) time of the trial method, the difference is large. For two numbers of size one billion the trial method may make a billion trials, while Euclid's algorithm makes at most about sixty divisions.
It is useful to return once more to the matter of input size. If the numbers have bit length ℓ, then log2 min(a, b) ≤ ℓ. So Euclid's algorithm makes a linear number of divisions in the bit length. The trial division in primality testing was exponential in the bit length. This is why Euclid's algorithm runs instantly even on numbers with hundreds of digits and is used freely in cryptography.
1.4.5The worst case: consecutive Fibonacci numbers
The halving bound is an upper bound; on most inputs the algorithm finishes earlier. But which inputs make the algorithm run longest? The numbers shrink most slowly when the quotient is 1 in every division. Then the remainder is the difference of the two numbers: r = a − b. Looking backward in this case, each number is the sum of the two numbers after it. This is exactly the rule of the Fibonacci sequence. The worst input is two consecutive Fibonacci numbers.
Tracing gcd(55, 34) (55 and 34 are consecutive Fibonacci numbers):
- 55 = 1 · 34 + 21
- 34 = 1 · 21 + 13
- 21 = 1 · 13 + 8
- 13 = 1 · 8 + 5
- 8 = 1 · 5 + 3
- 5 = 1 · 3 + 2
- 3 = 1 · 2 + 1
- 2 = 2 · 1 + 0
- Result: 8 divisions, gcd(55, 34) = 1. The remainders follow the Fibonacci sequence backward: 21, 13, 8, 5, 3, 2, 1, 0. Except for the last division, every quotient is 1. Although the numbers are as small as 55 and 34, the number of divisions exceeds the 5 divisions of the much larger
gcd(1599, 650).
The precise form of this observation is the theorem proved by Gabriel Lamé in 1844.
For a > b ≥ 1, if the call gcd(a, b) makes k divisions, then b ≥ F(k + 1). Accordingly, the number of divisions does not exceed five times the number of decimal digits of b.
Proof sketch. Let the remainders be r0 = a, r1 = b, r2, …, rk, rk+1 = 0; the i-th division is ri−1 = qi · ri + ri+1. The last nonzero remainder satisfies rk ≥ 1 = F(2). In the last division the remainder is 0 and rk−1 > rk, so qk ≥ 2 and rk−1 ≥ 2 = F(3). In every other division qi ≥ 1, so ri−1 ≥ ri + ri+1. Applied backward, this inequality shows that every remainder is at least a Fibonacci number, and we obtain r1 = b ≥ F(k + 1). Because Fibonacci numbers grow at a rate of about φ ≈ 1.618, k stays on the order of logφ b. ∎
The theorem is tight in the example gcd(55, 34): 8 divisions are made and b = 34 = F(9). That is, 34 is the smallest b that gives 8 divisions. The next pair gcd(89, 55) makes nine divisions. Among all pairs of numbers below 1000, the most divisions (14) are made by gcd(987, 610); 987 and 610 are also consecutive Fibonacci numbers. So even the worst case of Euclid's algorithm is logarithmic: Θ(log min(a, b)).
1.4.6Euclid with a loop
The recursive gcd calls itself as its last operation and passes the return value on unchanged. Such a recursion can be converted directly into a loop: in each round the pair (a, b) is replaced by (b, a mod b).
int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}The loop runs until b is zero. In each round the remainder r is computed first, then a is assigned the old b and b the remainder. The order of the assignments matters: if a = b were not done first, the old value of b would be lost. When the loop ends, a is the last nonzero remainder, that is, the GCD. Table 1.9 gives the loop rounds of the call gcd(1071, 462).
| Round | a (at start) | b (at start) | r = a % b | (a, b) at end of round |
|---|---|---|---|---|
| 1 | 1071 | 462 | 147 | (462, 147) |
| 2 | 462 | 147 | 21 | (147, 21) |
| 3 | 147 | 21 | 0 | (21, 0) |
| — | 21 | 0 | — | b == 0: return 21 |
The divisions are 1071 = 2 · 462 + 147, 462 = 3 · 147 + 21, and 147 = 7 · 21 + 0. The loop version makes the same number of divisions as the recursive version and has the same running time: O(log min(a, b)). The difference is in memory. The recursive version opens a stack frame for every call; the loop version uses only three variables and works with O(1) extra memory. Because the Java compiler does not turn tail recursion into a loop by itself, this transformation is done by hand.
1.5Common mistakes
The mistakes discussed in various places in these notes are collected here. All of them come from the same source: a detail of the code or of the analysis is set up without thinking about all inputs.
- Measuring time in seconds. Seconds depend on the machine, the language, and the load at that moment. Analysis uses the operation count as a function of n and how fast it grows. A measurement tells us something about the algorithm only when it is repeated at different values of n and the shape of the growth is seen.
- Forgetting memoization. Naive recursive Fibonacci is O(2n) because it solves the same subproblems over and over. Storing the results in an array brings the number of calls down to 2n − 1 and the time to O(n).
- Setting the √n bound too low. If
i < (int) Math.sqrt(n)is written, ⌊√n⌋ itself is not tried; perfect squares such as 9, 25, 49, and numbers such as 15 and 35 whose small factor equals exactly ⌊√n⌋ come out prime. The correct forms arei <= (int) Math.sqrt(n)or, as in the slides,i < (int) Math.sqrt(n) + 1. - Confusing the input size. In primality testing, n is the value of the number. For a number of b bits, √n = 2b/2; that is, trial division is exponential in the number of bits. For algorithms that take a single number as input, what the word “n” stands for must always be stated explicitly.
- Thinking matrix multiplication is n2. The result has n2 entries, but each entry needs n multiplications: n3 multiplications in all. With nested loops, one counts how many times in total the innermost operation runs.
- Not undoing the swap. If the second
swapis forgotten in permutation generation, the array gets corrupted; for{1, 2, 3}some permutations are printed twice and some are never produced. - Choosing the initial value independently of the input. Starting with
max = 0when looking for the largest element gives a wrong result on arrays whose elements are all negative. The initial value must be an element of the array itself. - Overlooking integer division. In Java the quotient of two
intvalues discards the fractional part. In computations such as an average, where a fractional result is expected, at least one operand must be adouble.
1.6Summary
- An algorithm is a finite sequence of precisely defined instructions for solving a problem. It takes input and produces output; its steps are definite, effective (doable), and finite; and it gives the correct result for every valid input. An algorithm is independent of the language; a program is its counterpart in a particular language.
- Algorithms fall into problem groups such as sorting, searching, graphs, and strings and compression. Divide and conquer, dynamic programming, greedy methods, backtracking, and branch and bound are design techniques. A deterministic algorithm always follows the same path on the same input; a randomized algorithm makes random choices in its steps.
- Algorithm analysis studies time and memory use as a function of the input size n. The running time T(n) is measured not in seconds but in the number of basic operations. For the sum of an array, line-by-line counting gives T(n) = 2n + 3.
- For large n, constant coefficients and lower-order terms become irrelevant and only the growth rate remains: 2n + 3 = Θ(n), 5n2 + 100n log2 n + 7 = Θ(n2).
- The order of growth: 1 < log n < √n < n < n log n < n2 < n3 < 2n < n!. A faster computer only shrinks the constant; a better algorithm changes the growth rate.
- Examples: printing the first element is O(1); finding the largest element takes Θ(n) time and O(1) extra memory; primality testing with odd divisors up to √n is O(√n); straightforward matrix multiplication is Θ(n3); generating all permutations is Θ(n · n!); naive recursive Fibonacci is Θ(1.618n), that is, exponential.
- Memoization stores the results of subproblems already computed; for Fibonacci it reduces the number of calls from 2F(n + 1) − 1 to 2n − 1 and the time to O(n). The price is O(n) memory.
- Euclid's algorithm rests on the identities gcd(a, b) = gcd(b, a mod b) and gcd(a, 0) = a. Its correctness comes from the common divisors of the two pairs being the same. Because the larger number at least halves every two steps, the time is O(log min(a, b)). The worst-case input is consecutive Fibonacci numbers (Lamé). The loop version runs in the same time with O(1) extra memory.
| Code | Input size | Operation counted | Time | Extra memory |
|---|---|---|---|---|
| sum of an array | number of elements n | comparisons, additions | 2n + 3 = Θ(n) | O(1) |
printFirst | number of elements n | comparison, access | O(1) | O(1) |
findMax | number of elements n | comparisons | n = Θ(n) | O(1) |
isPrime | value of the number n | divisions (%) | ≈ √n / 2 = O(√n) | O(1) |
multiply | matrix size n | multiplications | n3 = Θ(n3) | Θ(n2) (result) |
permute | number of elements n | lines printed | n! lines, Θ(n · n!) | O(n) (stack) |
fib | n | calls | 2F(n + 1) − 1 = Θ(1.618n) | O(n) (stack) |
fibMemo | n | calls | 2n − 1 = O(n) | O(n) |
gcd | a, b | divisions (%) | O(log min(a, b)) | recursive O(log min(a, b)), loop O(1) |
1.7Key terms
These are the terms introduced in this chapter.
- algorithm
- input
- output
- definiteness
- finiteness
- effectiveness
- correctness
- pseudocode
- deterministic algorithm
- randomized algorithm
- algorithm analysis
- time complexity
- space complexity
- input size
- running time
- worst case
- growth rate
- Big O notation
- Big Theta (Θ)
- constant time
- logarithmic
- linear
- linearithmic
- quadratic
- cubic
- exponential
- factorial
- primality test
- pseudo-polynomial
- swap
- recursion
- base case
- memoization
- Euclid's algorithm
1.8Test Yourself
“Let n be a positive integer. Repeat until n is 1: if n is even, n = n / 2; if it is odd, n = 3n + 1.” In how many steps does this procedure stop for n = 6? Can it be said for certain that the procedure is an algorithm?
Answer
For n = 6 the sequence is 6, 3, 10, 5, 16, 8, 4, 2, 1: it stops in 8 steps. The steps are definite and doable. But finiteness has not been proved for every n. This question is an unsolved problem in mathematics known as the Collatz conjecture. The procedure has been tried by computer up to very large numbers, and the sequence has always reached 1. But there is no proof that it stops for every positive integer. So it cannot be said for certain that the procedure is finite for every input, and hence that it is an algorithm.
In the code
for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) count++;, how many times doescount++run? What is the value for n = 10, and what is the complexity class?Answer
In round i the inner loop runs i times. The total is 0 + 1 + … + (n − 1) = n(n − 1) / 2. For n = 10 that is 10 · 9 / 2 = 45. Because the dominant term is n2 / 2, the class is Θ(n2).
In the call
isPrime(199), what islimit, which values ofiare tried in the loop, how many divisions are made, and what is the result?Answer
√199 ≈ 14.1, (int) √199 = 14,
limit = 15. The values tried are 3, 5, 7, 9, 11, 13; the remainders are 1, 4, 3, 1, 1, 4 respectively, and none is 0. After 6 divisions the loop ends and the method returnstrue: 199 is prime.With
multiply, anAof size 3 × 2 is multiplied by aBof size 2 × 3. What aren,m,p, what is the size of the result, and how many multiplications are made? What if the product were taken in the opposite order (B · A)?Answer
A · B:n = 3,m = 3,p = 2; the result is 3 × 3; 3 · 3 · 2 = 18 multiplications.B · A:n = 2,m = 2,p = 3; the result is 2 × 2; 2 · 2 · 3 = 12 multiplications. In matrix multiplication the order changes both the result and the operation count.In the call
permute({1, 2, 3, 4}, 0), on which line is the first permutation starting with 2 printed, and what is it? How many times is the method called in all?Answer
As long as 1 stays in the first position, the 3! = 6 permutations of the remaining three elements are printed. In the round k = 0, i = 1,
swap(0, 1)makes the array [2, 1, 3, 4], and this is the first line printed: line 7, [2, 1, 3, 4]. The number of calls is the sum of the calls at each level: 1 + 4 + 12 + 24 + 24 = 65.fib(7)andfibMemo(7)(memo array initially zero) are called separately. How many calls does each make, and what does it return?Answer
Both return F(7) = 13.
fib(7): C(7) = 2F(8) − 1 = 2 · 21 − 1 = 41 calls.fibMemo(7): 2 · 7 − 1 = 13 calls.How many divisions does
gcd(377, 233)make, and what is the result? How does this number compare with the bound given by Lamé's theorem?Answer
377 and 233 are consecutive Fibonacci numbers (F(14) and F(13)). The remainders are 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 0: 12 divisions, result 1. By the theorem, k divisions require b ≥ F(k + 1); since b = 233 = F(13), k ≤ 12. The example meets the bound exactly. The digit bound gives 5 · 3 = 15.
What does the recursive call
gcd(210, 84)return? How many calls are made, and how many frames deep does the call stack go at most?Answer
210 = 2 · 84 + 42, 84 = 2 · 42 + 0. The calls are
gcd(210, 84),gcd(84, 42),gcd(42, 0): 3 calls, 2 divisions, result 42. When the base case is reached the stack holds 3 frames.A computer is made 100 times faster. By what factor does the largest input solvable in the same time grow for a Θ(n2) algorithm? By how much does n grow for a Θ(2n) algorithm?
Answer
For the quadratic algorithm, the condition (kn)2 = 100 n2 gives k = 10: the input grows tenfold. For the exponential algorithm, the condition 2n + d = 100 · 2n gives d = log2 100 ≈ 6.6: n grows by only 6 (as an integer).
Two primes, one of 40 bits and one of 80 bits, are tested with
isPrime. About how many divisions are made for each? At 109 divisions per second, how long does the second take?Answer
The number of divisions is about √n / 2. For the 40-bit number n ≈ 240 and √n ≈ 220; the number of divisions is about 219 ≈ 524,000, and it finishes instantly. For the 80-bit number √n ≈ 240; the number of divisions is about 239 ≈ 5.5 · 1011, and it takes about 550 seconds, that is, more than nine minutes. When the number of bits doubles, the time grows about a millionfold: exponential growth in the bit length.
1.9Further reading
- D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms (3rd ed., 1997), Section 1.1: introduces the concept of an algorithm through Euclid's algorithm and discusses the properties of input, output, definiteness, finiteness, and effectiveness under the names used in these notes.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (4th ed., 2022), Chapters 1–3: give the place of algorithms in computing, the line-by-line analysis of insertion sort, and asymptotic notation with its formal definitions; Chapter 31 analyzes the running time of Euclid's algorithm with Fibonacci numbers.
- R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Section 1.4: shows, with Java examples, how to measure running time by experiments and explain the measurements with a mathematical model.
- J. Kleinberg and É. Tardos, Algorithm Design (2005), Chapter 2: treats polynomial time as the criterion of efficiency and compares common running times through example algorithms.
1.10References
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022.
- J. Kleinberg, É. Tardos, Algorithm Design, Pearson, 2005.
- D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed., Addison-Wesley, 1997.
- R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.
Related pages: Chapter 1 slides · Slides PDF · © Sercan Külcü. All rights reserved.