Algorithms: flowcharts, structured programming and complexity
Properties of an algorithm, flowcharts and pseudocode with Euclid's algorithm, the Böhm-Jacopini theorem, big-O notation and binary search.
An algorithm is a finite sequence of unambiguous instructions that solves a problem. The word comes from the name of the Persian mathematician al-Khwarizmi, and the first algorithm we know of, Euclid’s for the greatest common divisor, is more than two thousand years old. Before writing code it pays to design the algorithm: that is where you decide whether the program will be correct and fast. In this lesson we see how an algorithm is described, the basic structures of structured programming and how cost, that is complexity, is measured.
Properties of an algorithm
- Finiteness: it ends after a finite number of steps.
- Unambiguity: each step has a single meaning.
- Input and output: it receives data and produces a result.
- Effectiveness: each step can really be carried out with the available operations.
- Generality: it solves a class of problems, not a single case.
How to describe it: flowcharts and pseudocode
A flowchart represents the algorithm with blocks joined by arrows: ovals for start and end, parallelograms for input and output, rectangles for operations, diamonds for decisions.
Pseudocode describes the same algorithm in a language halfway between English and a programming language, more compact than the flowchart:
read a, b
while b ≠ 0:
r ← a mod b
a ← b
b ← r
write aWhy it works. Every common divisor of 
and 
also divides 
, and vice versa: so 
. Since 
, the second number shrinks at each step and reaches 0 in finitely many steps, and 
.
Structured programming
The Böhm-Jacopini theorem (1966, two Italian computer scientists) proves that any algorithm can be written using only three structures:
- sequence: one instruction after another;
- selection: if a condition is true do one thing, otherwise another (
if); - iteration: repeat while a condition is true (
while).
Arbitrary jumps (goto), which make code hard to follow, are not needed: this is the basis of structured programming, and of the C we will see from the next lesson.
Complexity
Two correct algorithms for the same problem can take very different times. Computational complexity measures how the number of operations grows as the size 
of the data grows. The 
notation is used: an algorithm is 
if for large it performs at most a number of operations proportional to 
.
| Complexity | Example |  |  |
|---|---|---|---|
 | accessing an array element | 1 | 1 |
 | binary search in a sorted array | 10 | 20 |
 | finding the maximum of an array |  |  |
 | merge sort, FFT |  |  |
 | bubble sort, direct DFT | |  |
 | trying every subset |  | impossible |
At a billion operations per second, operations take a quarter of an hour; take two hundredths of a second. Improving the algorithm matters far more than buying a faster computer.
Example: how many steps Euclid takes. Every two steps the first number at least halves (it is easy to prove), so the number of steps is at most about 
of the smaller number: . For 300-digit numbers, like those of RSA cryptography, a few thousand steps are enough, a fraction of a millisecond. Trying every divisor would be impossible.
Linear search and binary search
Searching for a value in an array of unsorted elements means looking at them one by one: . If the array is sorted you can do much better: look at the middle element, and depending on whether it is larger or smaller than the value sought, discard half the array. After 
steps 
elements remain, so 
steps are enough: 20 comparisons for a million elements, 30 for a billion.
/* returns the index of x in the sorted array v of n elements, or -1 */
int binary_search(const int v[], int n, int x)
{
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; /* avoids computing lo + hi, which could overflow */
if (v[mid] == x) return mid;
if (v[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}Computing mid as lo + (hi - lo) / 2 instead of (lo + hi) / 2 is not pedantry: with indices close to the largest value of an int, the sum would overflow. It is a bug that stayed for years in the standard libraries of several languages.
