Level:
Correct: 0
Incorrect: 0
Marks: 0/0
Exam Practice
Course:
Topics:
AQA GCSE Computer Science (Paper 1) Smart practice A mixed round aimed at your weak spots
Unit 1
3.1 Fundamentals of algorithms
Unit 2
3.2 Programming
Data types
Data types
Arithmetic operations in a programming language
Arithmetic operations, DIV and MOD
Relational operations in a programming language
Relational operations
Boolean operations in a programming language
Boolean operations in conditions
Data structures
Arrays and records
Input/output
Input and output
String handling operations in a programming language
String handling
Random number generation in a programming language
Random number generation
Structured programming and subroutines (procedures and functions)
Subroutines and structured programming
Avg
score:
–
Topics
done:
0/15

Efficiency of algorithms

Practise 25 exam-style questions on Efficiency of algorithms for AQA GCSE Computer Science (Paper 1). Write your answer as you would in the exam and get it marked in seconds against the mark scheme, point by point, with the Study Helper on hand if you get stuck.

  • 25 questions
  • 1–6 marks each
  • Instant marking
  • No sign-up needed
20 questions, marked as you go

Sample questions with model answers

Here are 4 of the questions in this topic, each with a model answer, an explanation of why it earns the marks and the mark scheme an examiner would use.

Question 1

1 mark

The time efficiency of the algorithm below is measured by counting how many times its loop body is executed.

x ← 1
WHILE x < 200
  x ← x * 3
ENDWHILE
OUTPUT x

How many times is the loop body executed?

Choose your answer.

  • 4
  • 5
  • 67
  • 200

Model answer

5

Explanation

x goes 3, 9, 27, 81 and then 243; after the fifth pass x is no longer less than 200, so the loop stops (and 243 is output). Choosing 4 forgets the last pass that takes x past 200. 67 is the number of passes if x went up by 3 each time instead of being multiplied by 3.

Mark scheme
  1. 1 mark

    5

    If more than one option is given, 0 marks. Mark is for AO2 (apply).

Question 2

2 marks

Two methods can be used to check whether a whole number n (greater than 2) is prime:
- Method 1 tests every whole number from 2 to n - 1 to see whether it divides n exactly.
- Method 2 tests the whole numbers from 2 upwards, but stops as soon as it finds one that divides n exactly.

Give a value of n between 20 and 30 for which both methods carry out the same number of tests, and explain why.

Model answer

n = 23. 23 is prime, so no number from 2 to 22 divides it exactly. Method 2 never finds a factor, so it never stops early and tests all 21 numbers, exactly like Method 1.

Explanation

Method 2 only saves time when it finds a factor before reaching n - 1. For a prime number there is no such factor, so both methods test every number from 2 to n - 1 (21 tests for 23, 27 for 29). This shows that how much more efficient an algorithm is can depend on the data it is given.

Mark scheme
  1. 1 mark

    23 // 29

    2 marks for AO2 (apply). A. both values given.

  2. 1 mark

    Because n is prime / has no factors other than 1 and itself, so Method 2 never finds a factor and never stops early (it also tests every number up to n - 1)

    This mark can be awarded with an incorrect value of n only if the explanation is about prime numbers.

Question 3

3 marks

Both algorithms below output True if the positive whole number entered is a square number (such as 9, which is 3 × 3), and False otherwise.

Algorithm A

n ← USERINPUT
square ← False
FOR i ← 1 TO n
  IF i * i = n THEN
    square ← True
  ENDIF
ENDFOR
OUTPUT square

Algorithm B

n ← USERINPUT
i ← 1
WHILE i * i < n
  i ← i + 1
ENDWHILE
IF i * i = n THEN
  OUTPUT True
ELSE
  OUTPUT False
ENDIF

The user enters 144. State how many times the loop body is executed in each algorithm, and explain why Algorithm B is more time efficient.

Model answer

Algorithm A: 144 times
Algorithm B: 11 times
B is more efficient because it stops as soon as i × i reaches n, so it only tries values up to the square root of 144 (12). A carries on testing every value of i up to 144, even after it has found the answer.

Explanation

In B, i goes from 1 up to 12 and the loop body runs 11 times, because the test 12 × 12 < 144 is false. A's FOR loop always runs n times, so for 144 it does 144 passes. Both output True, but B's work grows far more slowly as n gets bigger.

Mark scheme
  1. 1 mark

    Algorithm A: 144

    3 marks for AO2 (apply).

  2. 1 mark

    Algorithm B: 11

    R. 12 (i reaches 12, but the loop body only runs 11 times).

  3. 1 mark

    B stops as soon as i × i is no longer less than n / it only tries values up to the square root of n (12), whereas A tries every value from 1 to n

    NE. 'B uses a WHILE loop'.

Question 4

4 marks

A palindrome is a word that reads the same forwards and backwards. Both algorithms below check whether a word is a palindrome. Characters are indexed from 0.

Algorithm A

word ← USERINPUT
n ← LEN(word)
mismatches ← 0
FOR i ← 0 TO n - 1
  IF word[i] ≠ word[n - 1 - i] THEN
    mismatches ← mismatches + 1
  ENDIF
ENDFOR
IF mismatches = 0 THEN
  OUTPUT 'Palindrome'
ELSE
  OUTPUT 'Not a palindrome'
ENDIF

Algorithm B

word ← USERINPUT
left ← 0
right ← LEN(word) - 1
same ← True
WHILE left < right AND same = True
  IF word[left] ≠ word[right] THEN
    same ← False
  ENDIF
  left ← left + 1
  right ← right - 1
ENDWHILE
IF same = True THEN
  OUTPUT 'Palindrome'
ELSE
  OUTPUT 'Not a palindrome'
ENDIF

The user enters racecar. State how many times two characters are compared (≠) in each algorithm. Give two reasons why Algorithm B is more time efficient.

Model answer

Algorithm A: 7 comparisons
Algorithm B: 3 comparisons
Reason 1: B works in from both ends and stops at the middle, so it compares each pair of characters only once, whereas A compares every pair twice.
Reason 2: B stops as soon as it finds a pair that does not match, whereas A always checks every character.

Explanation

racecar has 7 letters, so A's FOR loop makes 7 comparisons; B compares r/r, a/a and c/c, and then left and right meet at the middle e. For a word such as robots, B stops after its first comparison (r and s do not match) while A still makes 6. The two reasons are different ideas: halving the comparisons, and stopping early.

Mark scheme
  1. 1 mark

    Algorithm A: 7

    4 marks for AO2 (apply).

  2. 1 mark

    Algorithm B: 3

  3. 1 mark

    B only compares characters up to the middle of the word / compares each pair once, whereas A compares every pair twice (and the middle character with itself)

  4. 1 mark

    B stops as soon as it finds a pair of characters that do not match, whereas A always carries on to the end

    Two different reasons are needed for these two marks.

Ready to try the rest? Every answer you write is marked against the mark scheme, so you can see exactly where the marks are.

Study Helper Hints first, answers after you try

Stuck on this one? Ask for a hint and I’ll point you in the right direction, without giving the answer away. Once you’ve checked your answer, I’ll show you how the marks are awarded.