Compare algorithm efficiency

What is Algorithm Efficiency?

When two algorithms solve the same problem correctly, one may still be more efficient than the other. At GCSE level, efficiency refers to time efficiency - how many steps an algorithm must perform to reach its answer. An algorithm that takes fewer steps is more time efficient. This matters because as the size of the input data grows, a less efficient algorithm can become dramatically slower - sometimes to the point of being unusable.

The simplest way to compare efficiency is to count the steps each algorithm takes for different amounts of input, then observe how quickly that count grows.

Single Loops vs Nested Loops

The number of loops in an algorithm - and how they are arranged - has a major effect on efficiency. The tabs below compare a single loop with a nested loop (a loop inside another loop) using step counts for growing input sizes.

This algorithm outputs every number from 1 to n. It uses a single loop.

i ← 1
WHILE i <= n
    OUTPUT i
    i ← i + 1
ENDWHILE

The loop body runs once per item in the input. If n = 5, the loop runs 5 times. If n = 100, it runs 100 times. The number of steps grows in line with n - this is described as linear growth.

More efficient Steps grow steadily: double the input, roughly double the steps.

This algorithm outputs every pair of numbers from 1 to n. It uses a nested loop - a loop inside another loop.

i ← 1
WHILE i <= n
    j ← 1
    WHILE j <= n
        OUTPUT i, j
        j ← j + 1
    ENDWHILE
    i ← i + 1
ENDWHILE

For every single step of the outer loop, the inner loop runs n times. Total steps = n × n = n². If n = 5, steps = 25. If n = 10, steps = 100. If n = 100, steps = 10,000. The number of steps grows much faster than the input - this is described as quadratic growth.

Less efficient Steps grow rapidly: double the input, roughly quadruple the steps.

The table below shows how the step counts compare as n increases. The gap between a single loop and a nested loop widens very quickly.

n (input size)	Single loop steps	Nested loop steps (n × n)
1	1	1
5	5	25
10	10	100
50	50	2,500
100	100	10,000

For small inputs the difference seems minor, but at n = 100 the nested loop performs 100× more steps. In a real system processing thousands of items, this difference is the gap between a program that runs in seconds and one that takes hours.

Deep Dive: Naming Efficiency

Computer scientists use Big O notation to describe how an algorithm's step count grows with input size. You do not need to calculate or derive this at GCSE, but it is useful to recognise the two labels that correspond to the algorithms above:

O(n) - "order n" - steps grow in proportion to the input size. A single loop is typically O(n). Sometimes called linear.
O(n²) - "order n squared" - steps grow in proportion to the square of the input size. A nested loop is typically O(n²). Sometimes called quadratic.

The key idea is simple: O(n) algorithms stay manageable as inputs grow; O(n²) algorithms can become very slow, very quickly. When comparing two correct algorithms, the one with fewer steps for large inputs is the more efficient choice.

Key Takeaways

Efficiency at GCSE means time efficiency - how many steps an algorithm takes relative to its input size.
A single loop runs once per item - if input doubles, steps roughly double (linear growth).
A nested loop runs n × n times - if input doubles, steps roughly quadruple (quadratic growth).
For small inputs, the difference in efficiency may be unnoticeable. For large inputs, it becomes very significant.
Two algorithms can be equally correct but have very different efficiencies - always consider step count when choosing between them.