# Algorithms: What’s the problem?

yourbasic.org

A good programmer describes algo­rithms in a form that can be effi­ciently exe­cuted by ma­chines and easily under­stood 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, clear 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 a1a2, ..., an of n numbers.
• Output: a permutation (reordering) a'1a'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 it’s 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 c1 n2, where c1 is a constant that depends on how well the algorithm is implemented.
• Quicksort requires roughly c2 n log2 n instructions, where c2 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.

1. Let's run Insertion sort on a fast computer that can execute 109 instructions per second. The algorithm is implemented by a skillful programmer and the constant c1 = 5.
2. Quicksort run will run on a much slower computer that can only execute 107 instructions per second. Also, the implementation is sloppy: c2 = 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.  