Efficiency of Algorithms — AQA GCSE CS (8525)

Spec & Goals 3 min

AQA Spec 3.1.2 · Efficiency of algorithms

By the end of this lesson you can:

Explain that efficiency means how many steps an algorithm takes.
Count the steps of two algorithms and decide which is more efficient.
Explain why we count steps rather than measure time in seconds.

Warm-Up 5 min

Last lesson you traced algorithms line by line. Counting those lines is the first step to measuring efficiency.

Quick starter

Two routes get Aisyah from home to school. Route A has 20 turns; Route B has 6 turns. Which route is simpler to follow, and why?

Reveal the answer

Route B — it takes fewer steps. An efficient algorithm is the same idea: the one that reaches the answer in fewer steps.

Key Concept — measuring efficiency 14 min

The efficiency of an algorithm is how many steps it takes to finish a task. For the same task, fewer steps means a more efficient algorithm.

Why we count steps, not seconds

We measure the number of steps, not the time in seconds. The same algorithm runs faster on a powerful computer and slower on an old one.

Steps grow with the input

The number of steps usually grows with the size of the input. Sorting 1,000 names takes more steps than sorting 10.

Worked Example — two ways to sum 1 to n 12 min

Problem: add up the numbers from 1 to n. We compare a loop with a formula.

Algorithm A — a loop

AQA pseudo-code

total ← 0
FOR i ← 1 TO n
    total ← total + i
ENDFOR
OUTPUT total

The same algorithm in Python

total = 0
for i in range(1, n + 1):
    total = total + i
print(total)

The loop body runs once for each number, so it takes about n steps.

Algorithm B — a formula

AQA pseudo-code

total ← n * (n + 1) / 2
OUTPUT total

The same algorithm in Python

total = n * (n + 1) / 2
print(total)

This does the same sum in just a few steps, whatever n is.

Counting steps for n = 100

Algorithm	Steps for n = 100	Steps in general
A — loop	about 100 (one per number)	about `n`
B — formula	a few (one calculation)	a few (constant)

Both give the same answer (5050), but Algorithm B uses far fewer steps. The formula is more efficient, and the gap grows as n gets larger.

Try It Yourself 12 min

🟢 Easy

Goal: Count the steps. How many times does the loop body run in this algorithm?

FOR i ← 1 TO 50
    OUTPUT i
ENDFOR

Hint: the loop runs once for each value from 1 to 50.

🟡 Medium

Goal: Two algorithms both find the largest of n numbers. Algorithm X checks every number once; Algorithm Y sorts the whole list first, then takes the last value. Which is more efficient, and why?

Hint: compare the number of steps each one takes for a long list.

🔴 Stretch

Goal: Explain why measuring an algorithm by counting steps is fairer than timing it with a stopwatch on your laptop.

Hint: think about what changes if you run the same code on a faster machine.

📝 Exam Practice 10 min

Answer the way the examiner expects — the command word and the marks tell you how much to write.

Explain[2 marks]

Look again at the two algorithms that sum 1 to n. State which is more efficient and explain why.

Mark scheme

Algorithm B / the formula is more efficient (1).
Because it uses fewer steps / a constant (small) number of steps whatever the input size, whereas the loop runs about n times (1).

Give[1 mark]

Give one reason we measure the efficiency of an algorithm by counting steps rather than by timing it in seconds.

Mark scheme

The time in seconds depends on the computer / hardware, so counting steps gives a fair comparison independent of the machine (1).

Identify[1 mark]

Which statement is correct? Choose one.

A — A more efficient algorithm always uses more steps.
B — For the same task, fewer steps means a more efficient algorithm.
C — Efficiency only depends on the speed of the computer.
D — The number of steps never changes with the input size.

Mark scheme

B (1) — for the same task, fewer steps is more efficient.

Recap & Key Terms 3 min

Efficiency is how many steps an algorithm takes. For the same task, fewer steps is more efficient. We count steps, not seconds, because computers run at different speeds. The number of steps usually grows with the input size.

Efficiency: A measure of how many steps (or how much memory) an algorithm uses to complete a task.
Number of steps: The count of operations an algorithm performs — the fair way to compare two algorithms.
Input size: How much data the algorithm works on; larger inputs usually mean more steps.

Homework 1 min

Task (≤ 15 min): An algorithm prints every number from 1 to n. State how many steps it takes for n = 200, and explain whether the steps grow with the input size.

Model answer

About 200 steps — one per number. Award marks for: stating about 200 / n steps (1), and explaining that the number of steps grows as the input size n grows (1).