Algorithms: What’s the problem?
A good programmer describes algorithms in a form that can be efficiently executed by machines and easily understood by humans.
Algorithms and programs are pretty much the same thing – the main difference is that we can talk about algorithms without relying on a programming language. An algorithm invented today will be equally as useful when the last Java programmer has logged out. Here is an attempt at a formal definition.
An algorithm is a stepwise procedure of well-defined executable instructions intended to perform a task or solve a problem, often with the added requirement that the procedure must come to a stop.
A programmer’s job is to design and implement algorithms that are correct, simple and efficient.
Problems
Algorithms are commonly used to solve certain types of computational problems. We can often describe such a problem by specifying a relationship between input and output.
The sorting problem, for example, can be described like this:
- Input: a sequence a_{1}, a_{2}, ..., a_{n} of n numbers.
- Output: a permutation (reordering) a'_{1}, a'_{2}, ..., a'_{n} of the input, which satisfies the property a'_{1} ≤ a'_{2} ≤ ... ≤ a'_{n}.
As an example: given the input sequence 12, 24, 13, 12, 8 a sorting algorithm must produce the output sequence 8, 12, 12, 13, 24. One such specific example of input for a problem is called an instance of the problem.
We say that an algorithm is correct if the algorithmic procedure stops for each problem instance and returns the required output. The algorithm solves the problem.
Pseudocode
When talking and writing about algorithms its convenient to use pseudocode instead of executable code.
Pseudocode is a compact and informal high-level description of an algorithm intended for humans rather than machines.
In pseudocode you can omit details that are easy to figure out for a human, such as variable declarations and system-specific function calls. You can also use natural language and mathematical notation.
For obvious reasons, there is no standard for writing pseudocode, but here is a typical example. First take a look at the code written in Go.
// Sum returns the sum 1 + 2 + ... + n, where n ≥ 1.
func Sum(n int) int {
var sum int
for i := 1; i <= n; i++ {
sum += i
}
return sum
}
The same algorithm described in pseudocode might look like this.
// Returns the sum 1 + 2 + ... + n, where n ≥ 1. Algorithm sum(n) sum ← 0 for i ← 1 to n sum += i return sum
Efficiency
Different algorithms that solve the same problem can have large performance differences. Here is a typical situation.
- The number of machine instructions required to sort n numbers with Insertion sort can be approximated with the formula c_{1 }n^{2}, where c_{1} is a constant that depends on how well the algorithm is implemented.
- Quicksort requires roughly c_{2 }n log_{2} n instructions, where c_{2} is an implementation-dependent constant.
From this we can see that Quicksort is much faster than Insertion sort when n is large. This holds true even if we use an incompetent implementation of Quicksort running on a slow computer.
Example
The differences become painfully obvious when we plug in some actual values in the formulas.
- Let's run Insertion sort on a fast computer that can execute 10^{9} instructions per second. The algorithm is implemented by a skillful programmer and the constant c_{1} = 5.
- Quicksort run will run on a much slower computer that can only execute 10^{7} instructions per second. Also, the implementation is sloppy: c_{2} = 100.
For small instances of the sorting problem, the faster computer wins.
- If n = 1000 it takes about 5 ms to sort using in the first case,
- while the second case takes 100 ms.
For larger instances, the picture is very different.
- If n = 1,000,000, the first case takes more than an hour (5000 s),
- while the second case takes less than five minutes (200 s).
For even larger problem instances, the differences are even bigger and the choice of algorithm becomes even more critical.
Further reading
See Time complexity: Count your steps for more on estimating algorithm performance.
See Top 3 Quicksort optimizations for a fast Quicksort implementation that uses Insertion sort to improve performance.