Practise Efficiency of algorithms. 11 exam-style questions plus unlimited generated ones on this subtopic, at up to four difficulty levels, with full mark schemes and a progress tracker. Free, no account needed.
Cover the answers and test yourself. The app has these as flashcards that come back just before you'd forget them.
Define the term 'efficiency' when it is used about an algorithm.
How much time (how many steps) and memory the algorithm uses to solve the problem.
Sample questions
Written for this site in the style of Edexcel exam questions. They are not taken from real past papers.
Question 1Easy4 marks
Different algorithms can be used to solve the same problem.
(a) Define the term 'efficiency' when it is used about an algorithm.[1]
(b) Give two ways of comparing the efficiency of two algorithms that solve the same problem.[2]
(c) Identify the algorithm that is usually the most efficient way to find an item in a large sorted list.[1]
Linear search
Binary search
Bubble sort
Merge sort
Show the answer and mark scheme
(a)Answer: How much time (how many steps) and memory the algorithm uses to solve the problem.
how much time / how many steps (e.g. comparisons) and memory an algorithm uses
(b)Answer: Compare the number of comparisons they make and the amount of memory they use.
the number of comparisons made
the number of passes through a loop
the amount of memory used
the time taken to run with the same data
(c)Answer: Binary search
Question 2Medium5 marks
This program checks whether a product code is in a list.
01 codes = ["K7", "M2", "A9", "B4", "T1", "Z3", "Q8", "C5"]
02 target = "B4"
03 found = False
04 for code in codes:
05 if code == target:
06 found = True
07 print(found)
(a) State how many times line 05 is executed.[1]
(b) Amend the program so that it stops checking as soon as the target is found.[3]
(c) State how many comparisons your program makes for this target.[1]
Show the answer and mark scheme
(a)Answer: 8
8
(b)Answer:
codes = ["K7", "M2", "A9", "B4", "T1", "Z3", "Q8", "C5"]
target = "B4"
found = False
index = 0
while index < len(codes) and not found:
if codes[index] == target:
found = True
index = index + 1
print(found)
uses a condition-controlled loop / uses the flag in the loop condition
the loop stops when the target is found or the end of the list is reached
the index is increased on each pass and each item is compared with the target
(c)Answer: 4
4
Question 3Hard7 marks
This function checks whether a list of usernames contains any duplicates.
01 def hasDuplicate(names):
02 for i in range(len(names)):
03 for j in range(i + 1, len(names)):
04 if names[i] == names[j]:
05 return True
06 return False
(a) State the maximum number of times line 04 is executed for a list of 5 names.[1]
(b) Calculate the maximum number of times line 04 is executed for a list of 100 names.[2]
(c) Another method first sorts the list, then compares each name only with the next name. Explain why this method needs far fewer comparisons after sorting, and state how many comparisons it needs, after sorting, for a list of 100 names.[3]
(d) State when the first function makes fewer comparisons than its maximum.[1]
Show the answer and mark scheme
(a)Answer: 10
10
(b)Answer: 4950 (99 + 98 + … + 1 = 99 × 100 ÷ 2)
99 + 98 + … + 2 + 1 (or the idea of adding the comparisons for each i)
4950
(c)Answer: After sorting, any duplicate names are next to each other, so only neighbouring pairs need to be compared: 99 comparisons.
after sorting, duplicates are next to each other
so only adjacent pairs need to be compared
99
(d)Answer: When a duplicate is found before the end, because the function returns straight away.
when a duplicate is found early (it returns True straight away)