3.1.2 Efficiency of Algorithms

Efficiency - A measure to compare two different algorithms that solve the same problem.
A more efficient algorithm is a better choice. Efficiency can be measured in a number
of different ways, but at GCSE level, you only need to worry about TIME efficiency.
An algorithm that can be executed in 20 instructions, is more efficient than one that
takes 30 instructions.

• The following trinket windows demonstrate the efficiency of an algorithm to solve a simple sorting problem.
• These two algorithms use different methods to swap items in a list:
  • Method 1: Temporary Variable:

• Method 2: In-line place swap:

• As we can see from the two algorithms above, the first method that uses a temporary variable to store a list item solves the sort problem using 9 lines of code.
• The second method that uses the In-line place swap to switch the list items only uses 7 lines of code.
• Not a huge difference, but when you are trying to solve a big problem that involves hundreds of lines of code, being more efficient with your code will:
  1. Reduce the number of lines of code,
  2. Be easier to debug,
  3. Will execute alot faster.

In the next two topics 3.1.3 and 3.1.4, we will look in more detail at comparing the
efficiency of algorithms and explain how some algorithms are more efficient than
others in solving the same problem.

• In most cases with GCSE exam questions, you may be provided with an algorithm and asked what it does or what the output would be.
• So you need to be able to read and understand algorithms.

For Example

Interpreting an algorithm works best when you do so, one line at a time, as a computer
would. A TRACE TABLE can and should be used to keep track of variables that change
throughout the algorithm.
The variables in this program are called 'number' and 'result'.

Trace Table

loop	number	result	Explanation
1	3	1	In lines '1' and '2', the variables are given these values.
2	3	1	In line '3', the loop starts and will run as long as'number' is greater than '1'.
3	3	3	In line '4', 'result' is set to itself, multiplied by 'number'. '1' times '3' is '3'.
4	2	3	Line '5' says that 'number' should have '1' subtracted from it.
5	2	3	Line '6' is the end of the loop, so we go back to the start.
6	2	3	'number' is still greater than '1', so the loop runs again.
7	2	6	Line '4', 'result' is set to itself, multiplied by 'number'. '2' times '3' is '6'.
8	1	6	Line '5' says that 'number' should have '1' subtracted from it.
9	1	6	Line '6' is the end of the loop, so we go back to the start.
10	1	6	Loop will not run again, as 'number' is not greater than '1'. so we exit the loop.
11	1	6	'result' is displayed, which is currently '6'.

Looking at an algorithm as a whole can be daunting, but follow it one line at a time makes
it much simpler, no individual line is particularly complicated, and errors can be easily
identified.