Problem Solving: Comparing algorithms

Comparing algorithms

An algorithm is a step-by-step set of instructions to solve a specific problem and it is important to understand that the same problem can be solved with a variety of algorithms.

This section of the specification is concerned with the criteria that is used to chose the most suitable algorithm for a set of a given problem out of a set of algorithms for the same problem.

In other words, how can we measure the efficiency of a given algorithm, so it can be compared with a different algorithm which solves the same problem?

A very common problem is the searching of an item in a set of items. This may be a name in a very large database for people.

One of the algorithms to solve this problem is shown in the illustration below:

[image of linear search flowchart to be follow here]

[link to Python implementation to follow below]

Another algorithm for solving the same problem is shown in illustrations below.

[image of binary search flowchart to be added here]

[link to Python implementation added below]

Both algorithms are solving the same problem. Which one should be chosen to be coded as a program to solve the problem?

In order to decide which algorithm to chose over another, they are compared in terms of their efficiency: the time it takes to find the solution and the resources which are consumed in the process. Consider the choice between different cars, where you might consider both the speed it will take to travel from one destination to another and the fuel it will consume during the journey.

Space-wise efficiency

That is the amount of (memory) space the algorithm will take up before it terminates with the correct solution.

In order to identify the space-wise efficiency we need to look at the amount of data structures used as the algorithm is running. When considering space-wise efficiency, the aim is to utilise data structures which take up the least amount in memory.

Examples:

• populating a list with variables of type real will be space-wise inefficient, when it is clear that only whole numbers (integers) will ever be needed to solve the problem.
• initialising an array with a length of 1000 will be space-wise inefficient, when it is clear that the maximum elements to be stores will be 100.

Time-wise efficiency

This is the amount of time it takes for the algorithm to terminate with the correct solution.

Any measure of time will depend on other factors, like

• the particular version and type of programming language used to implement the algorithm;
• the hardware specification on which the implementation will be running;
• and of course the input to the algorithm, e.g. searching through a very very large set will take longer that searching through a short set and searching for an item which does not exist in a set will take longer than searching for an item which is present in a given set.

Clearly, it is important to reduce these dependencies to a minimum when comparing different algorithms. Both the programming language and hardware used are subject to changes over time. Hence, it is generally agreed that any comparison should not take these factors into consideration.

This leaves us with the size of the input as the only dependency we want to allow when consider the time it will take for the algorithm to terminate with the correct answer.

In other words, we want to find a function f(n), where n is the size of the input, e.g. the length of the list to be searched. The function uses the number of computational steps necessary for the algorithm to terminate.

Significant computational steps

In order to eliminate dependencies only the following steps are considered when calculating efficiency:

• memory access - that is any memory look up, e.g. calling a variable
• assignment
• any arithmetic expression
• comparison

Questions relating to the comparison of algorithms Consider the following algorithm: number1 <- INPUT number2 <- INPUT sum1 <- number1 + number2 number3 <- INPUT sum2 <- sum1 + number3 Count the number of computational steps in the algorithm Answer: 7 Optimise the algorithm in terms of space. Answer: number1 <- INPUT number2 <- INPUT number3 <- INPUT sum <- number1 + number2 + number3