Revision Library

revisionlibrary.co.uk

A-Level · Component 02: Algorithms and Programming

A2.3 Algorithms: Complexity, Searching and Sorting

OCR H446 · Calculators not allowed · about 120 minutes

Total Marks

Name: _______________________________ Date: ____ / ____ / ______

Answer ALL questions. Show all your working.

Efficient algorithms matter because the same task can be solved in many different ways, and some methods take far longer or use far more memory than others as the amount of data grows. This question tests your understanding of the basic ideas used to measure and describe algorithm efficiency.

(a)State what is meant by the time complexity of an algorithm.(2)

(b)Each description below describes how the number of operations an algorithm performs changes as the input size n increases. Write the correct Big O notation (A-D) next to each description.

Big O notation:
A) O(1)
B) O(n)
C) O(log n)
D) O(n²)

Descriptions:
(i) The number of operations stays the same no matter how large n becomes.
(ii) The number of operations roughly doubles each time n doubles.
(iii) The number of operations increases by only a fixed amount each time n doubles (e.g. halving the remaining search space each step).
(iv) The number of operations roughly quadruples each time n doubles.(4)

(c)Explain why Big O notation usually describes the worst-case number of operations rather than the best-case.(2)

(d)An algorithm contains two nested loops, each running from 1 to n. Which Big O notation describes its time complexity?(1)

A) O(n)
B) O(log n)
C) O(n²)
D) O(2n)

(Total for Question 1 is 9 marks)

A stock-control system for a small hardware shop in Leeds stores unsold item codes in an array called stock. The array is not sorted. All arrays in this paper are indexed from 0, so an array with n items has indices 0 to n - 1. Pseudocode follows OCR's Exam Reference Language conventions (assignment <-, iteration FOR ... NEXT / WHILE ... ENDWHILE / DO ... UNTIL, selection IF ... ENDIF).

FUNCTION LinearSearch(stock, target) RETURNS INTEGER
  FOR i <- 0 TO LEN(stock) - 1
    IF stock[i] = target THEN
      RETURN i
    ENDIF
  NEXT i
  RETURN -1
ENDFUNCTION

stock = [12, 7, 19, 3, 25, 8]

(a)Complete the trace table below to show LinearSearch(stock, 25) being called. Add a row for each value of i tested, showing stock[i] and whether stock[i] = target is true or false.

i	stock[i]	stock[i] = target?
0
1
2
3
4

(5)

(b)State the value returned by the function call in part (a).(1)

(c)The array is now searched for the value 30, which is not present. State the number of times the condition stock[i] = target is tested, and give the value returned by the function.(2)

(d)State, using Big O notation, the worst-case time complexity of linear search on a list of n items.(1)

(Total for Question 2 is 9 marks)

A school's exam-results system stores candidate numbers in ascending order in the array numbers. Binary search can be used because the array is sorted.

numbers = [3, 7, 12, 15, 19, 23, 28, 34, 41, 50] (indices 0 to 9)

FUNCTION BinarySearch(numbers, target) RETURNS INTEGER
  low <- 0
  high <- LEN(numbers) - 1
  WHILE low <= high
    mid <- (low + high) DIV 2
    IF numbers[mid] = target THEN
      RETURN mid
    ELSE IF numbers[mid] < target THEN
      low <- ______
    ELSE
      high <- ______
    ENDIF
  ENDWHILE
  RETURN -1
ENDFUNCTION

(a)Write the missing pseudocode for the two blank lines above, so that the algorithm correctly narrows the search range.(2)

(b)Complete the trace table below for the call BinarySearch(numbers, 34).

low	high	mid	numbers[mid]	result of comparison

(4)

(c)State the index returned, and the number of times numbers[mid] is compared with the target.(2)

(d)Each element of numbers is stored using 2 bytes, and the array starts at hexadecimal memory address 0x4000. Calculate the hexadecimal memory address of the element found in part (c).(2)

(e)Give the 8-bit binary representation of the byte offset (14) used in the calculation in part (d).(1)

(Total for Question 3 is 11 marks)

A car park's number-plate recognition system checks whether a scanned number plate matches one already stored in a list.

(a)The list of stored number plates is not kept in any particular order. Explain why binary search could not be used to search this list directly, and state one thing that would need to be done first if binary search were to be used.(2)

(b)The car park has 1000 stored number plates. Calculate the maximum number of comparisons linear search would need to make to determine that a scanned plate is not in the list.(1)

(c)Once sorted, the maximum number of comparisons binary search needs for a list of n items can be found using ceil(log2(n + 1)). Calculate the maximum number of comparisons needed to search the sorted list of 1000 number plates.(2)

(d)State, giving a reason based on your answers to (b) and (c), which search algorithm is more time-efficient for this large list.(2)

(Total for Question 4 is 7 marks)

A DIY store in Cardiff records the prices (in pounds) of five items on a shelf label strip in the order [5, 2, 9, 1, 6]. They are sorted using the bubble sort algorithm below.

PROCEDURE BubbleSort(list)
  n <- LEN(list)
  DO
    swapped <- FALSE
    FOR i <- 0 TO n - 2
      IF list[i] > list[i + 1] THEN
        temp <- list[i]
        list[i] <- list[i + 1]
        list[i + 1] <- temp
        swapped <- TRUE
      ENDIF
    NEXT i
    n <- n - 1
  UNTIL swapped = FALSE
ENDPROCEDURE

(a)Explain the purpose of the swapped flag in the pseudocode above.(2)

(b)Complete the trace table below for BubbleSort([5, 2, 9, 1, 6]), showing the contents of the list, the value of swapped, and the value of n at the end of each full pass.

pass	list at end of pass	swapped	n
1
2
3
4

(6)

(c)State the total number of comparisons and the total number of swaps made during the whole sort in part (b).(2)

(d)Explain how the algorithm knows to stop after pass 4 rather than continuing to check further passes.(2)

(Total for Question 5 is 12 marks)

A leisure centre stores four booking reference numbers [8, 3, 6, 1] which must be sorted into ascending order using insertion sort.

FUNCTION InsertionSort(list)
  FOR i <- 1 TO LEN(list) - 1
    current <- list[i]
    j <- i - 1
    WHILE j >= 0 AND list[j] > current
      ______
      j <- j - 1
    ENDWHILE
    list[j + 1] <- current
  NEXT i
ENDFUNCTION

(a)Using the pseudocode above, explain how insertion sort builds up the sorted part of the list as i increases.(2)

(b)Complete the trace table below for InsertionSort([8, 3, 6, 1]), showing the value of current and the list contents at the end of each iteration of the outer FOR loop (i = 1, 2, 3).

i	current	list at end of this iteration
1
2
3

(6)

(c)State the final sorted list produced.(1)

(d)Write the missing line of pseudocode (marked ______) needed inside the WHILE loop so the algorithm shifts elements correctly.(2)

(Total for Question 6 is 11 marks)

A playlist of 8 song lengths (in seconds) needs to be sorted using merge sort: [230, 180, 340, 95, 410, 150, 275, 60].

(a)Describe what happens during the divide stage and the merge (conquer) stage when merge sort sorts this playlist.(3)

(b)State how many times the playlist of 8 songs must be split before every sub-list contains a single element.(1)

(c)Explain why merge sort has a time complexity of O(n log n).(3)

(Total for Question 7 is 7 marks)

A library keeps an array titles of book titles sorted alphabetically. When a new book arrives, the system needs to find the position where the new title should be inserted so that titles stays in alphabetical order. If the title is already present, the function should return its existing index instead of inserting a duplicate.

(a)Write a function FindInsertPosition(titles, newTitle) RETURNS INTEGER, using a binary-search approach (rather than checking every element in turn), that:
- returns the index of newTitle if it is already present in titles, or
- otherwise returns the index at which newTitle should be inserted to keep the array sorted.

You may assume string comparisons (e.g. titles[mid] < newTitle) compare alphabetical order correctly. Use OCR pseudocode conventions. Marks are awarded for correct logic; minor syntax errors will be ignored.(6)

(Total for Question 8 is 6 marks)

Each pseudocode fragment below processes a list of n items. All arrays are indexed from 0.

(a)Fragment A:

FOR i <- 0 TO n - 1
  OUTPUT list[i]
NEXT i

State the Big O time complexity of Fragment A in terms of n, and briefly justify your answer.(2)

(b)Fragment B:

FOR i <- 0 TO n - 1
  FOR j <- 0 TO n - 1
    OUTPUT list[i] + list[j]
  NEXT j
NEXT i

State the Big O time complexity of Fragment B in terms of n, and briefly justify your answer.(2)

(c)Fragment C:

count <- n
WHILE count > 1
  count <- count DIV 2
  OUTPUT count
ENDWHILE

State the Big O time complexity of Fragment C in terms of n, and briefly justify your answer.(2)

(d)Fragment D:

FOR i <- 0 TO n - 1
  low <- 0
  high <- n - 1
  WHILE low <= high
    mid <- (low + high) DIV 2
    ...
  ENDWHILE
NEXT i

State the Big O time complexity of Fragment D in terms of n, and briefly justify your answer.(2)

(Total for Question 9 is 8 marks)

The table below lists five algorithms covered in this topic.

(a)Complete the table below by writing the worst-case time complexity of each algorithm, using Big O notation.

Algorithm	Worst-case time complexity
Linear search
Binary search
Bubble sort
Insertion sort
Merge sort

(5)

(b)State, for each of bubble sort, insertion sort and merge sort, whether it requires significant additional (auxiliary) memory beyond the original list, or whether it can sort in place using only a small, constant amount of extra memory.(3)

(c)A shop assistant has a list of 20 till receipts that are already almost fully sorted by value, with only two receipts out of place. State, with a justification, which of bubble sort or insertion sort would typically perform fewer operations on this nearly-sorted list.(2)

(Total for Question 10 is 10 marks)

A supermarket's loyalty-card database holds 2,000,000 customer records, sorted by customer ID. Throughout the day, staff repeatedly need to search for a customer's record by ID. Every night, a batch of new customer records is added, and the whole file must then be back in ID order ready for the next day's searching.

(a)Discuss which searching algorithm and which sorting algorithm would be most appropriate for this system, justifying your recommendation by referring to the time complexity of the algorithms you have studied in this topic.(6)

(Total for Question 11 is 6 marks)

For merge sort, the maximum number of key comparisons C(n) needed to sort a list of n elements (where n is a power of 2) can be modelled by the recurrence relation:

C(n) = 2 x C(n / 2) + (n - 1), with C(1) = 0

This reflects sorting two half-lists (each needing C(n/2) comparisons) and then merging them together, which needs at most (n - 1) comparisons.

(a)Use the recurrence relation to calculate C(2) and C(4).(3)

(b)Hence show that C(8) = 17, giving the value of C(n) at each stage of your working.(2)

(c)State whether this result is consistent with merge sort having a time complexity of O(n log n), giving a reason.(1)

(Total for Question 12 is 6 marks)

Mark scheme · A2.3 Algorithms: Complexity, Searching and Sorting

Question 1

(a) B1 a measure of the number of steps/operations (or run time) an algorithm takes (oe)
(a) B1 as the size of the input, n, increases
(a) Answer: Time complexity describes how the number of operations (or running time) an algorithm needs increases as the size of its input, n, increases.
(b) B1 (i) A cao
(b) B1 (ii) B cao
(b) B1 (iii) C cao
(b) B1 (iv) D cao
(b) Answer: (i) A (ii) B (iii) C (iv) D
(c) B1 it gives a guaranteed upper bound on the number of operations (oe)
(c) B1 which holds true whatever the specific input data is, not just for a lucky/typical case (oe)
(c) Answer: It guarantees the algorithm will never perform worse than this figure, regardless of the specific input data given, whereas the best case may rarely occur in practice.
(d) B1 C
(d) Answer: C) O(n²)

Question 2

(a) B1 i=0: stock[0]=12, false
(a) B1 i=1: stock[1]=7, false
(a) B1 i=2: stock[2]=19, false
(a) B1 i=3: stock[3]=3, false
(a) B1 i=4: stock[4]=25, true (loop stops, RETURN 4)
(a) Answer: i=0 (12,F), i=1 (7,F), i=2 (19,F), i=3 (3,F), i=4 (25,T) -> returns 4
(b) B1 4 ft from (a)
(b) Answer: 4
(c) B1 6 comparisons made (every element is tested since the target is absent)
(c) B1 returns -1
(c) Answer: 6 comparisons are made; the function returns -1.
(d) B1 O(n)
(d) Answer: O(n)

Question 3

(a) B1 low <- mid + 1
(a) B1 high <- mid - 1
(a) Answer: low <- mid + 1 ; high <- mid - 1
(b) B1 row 1: low=0, high=9, mid=4
(b) B1 row 1: numbers[4]=19, 19 < 34 so low <- 5
(b) B1 row 2: low=5, high=9, mid=7
(b) B1 row 2: numbers[7]=34, 34 = 34 so RETURN 7
(b) Answer: Row1: low=0,high=9,mid=4,numbers[4]=19 (< target, low<-5). Row2: low=5,high=9,mid=7,numbers[7]=34 (= target, return 7).
(c) B1 index 7 ft from (b)
(c) B1 2 comparisons ft from (b)
(c) Answer: Index 7 is returned; 2 comparisons are made.
(d) M1 address = base + (index x size) = 0x4000 + (7 x 2)
(d) A1 0x400E cao
(d) Answer: 0x400E
(e) B1 00001110
(e) Answer: 00001110

Question 4

(a) B1 binary search requires the data to be sorted (in order), as it relies on discarding half the remaining items each time (oe)
(a) B1 the list would need to be sorted first (e.g. using a sorting algorithm) before binary search could be applied
(a) Answer: Binary search needs the list to be in order so it can repeatedly halve the search space; an unsorted list would first need to be sorted before binary search could be used.
(b) B1 1000
(b) Answer: 1000
(c) M1 log2(1001) = awrt 9.97
(c) A1 ceil(9.97) = 10 cao
(c) Answer: 10
(d) B1 binary search (oe)
(d) B1 because it needs far fewer comparisons (10 compared with 1000), as O(log n) grows far more slowly than O(n) as n increases (oe)
(d) Answer: Binary search, because it needs only 10 comparisons in the worst case compared with 1000 for linear search, reflecting O(log n) growing much more slowly than O(n).

Question 5

(a) B1 swapped is set to TRUE whenever a swap is made during a pass
(a) B1 if no swaps occur during a pass, the list must already be sorted, so the algorithm can stop early (avoiding unnecessary further passes)
(a) Answer: It allows the algorithm to detect when a full pass makes no swaps, meaning the list is already sorted, so it can stop instead of running unnecessary further passes.
(b) B1 pass 1: list = [2, 5, 1, 6, 9]
(b) B1 pass 2: list = [2, 1, 5, 6, 9]
(b) B1 pass 3: list = [1, 2, 5, 6, 9]
(b) B1 pass 4: list = [1, 2, 5, 6, 9] (unchanged)
(b) B1 swapped correctly shown as TRUE, TRUE, TRUE, FALSE for passes 1-4
(b) B1 n correctly shown decreasing: 4, 3, 2, 1 at the end of passes 1-4
(b) Answer: Pass1 [2,5,1,6,9] swapped=T n=4; Pass2 [2,1,5,6,9] swapped=T n=3; Pass3 [1,2,5,6,9] swapped=T n=2; Pass4 [1,2,5,6,9] swapped=F n=1
(c) B1 10 comparisons ft
(c) B1 5 swaps ft
(c) Answer: 10 comparisons; 5 swaps.
(d) B1 on pass 4 no elements are out of order, so no swaps take place and swapped remains FALSE
(d) B1 the DO...UNTIL loop condition (UNTIL swapped = FALSE) is then met, so the loop, and the algorithm, ends
(d) Answer: In pass 4 the list is already fully sorted, so no swaps occur and swapped stays FALSE; this satisfies the UNTIL swapped = FALSE condition, ending the loop.

Question 6

(a) B1 at each value of i, the element current = list[i] is removed and compared backwards against the already-sorted elements to its left
(a) B1 elements greater than current are shifted one place to the right until the correct position is found, and current is then inserted there
(a) Answer: For each i, the element current is taken out and compared with the sorted elements before it; any elements greater than current are shifted right until the correct gap is found, and current is inserted there.
(b) B1 i=1: current = 3
(b) B1 i=1: list = [3, 8, 6, 1]
(b) B1 i=2: current = 6
(b) B1 i=2: list = [3, 6, 8, 1]
(b) B1 i=3: current = 1
(b) B1 i=3: list = [1, 3, 6, 8]
(b) Answer: i=1: current=3, list=[3,8,6,1]; i=2: current=6, list=[3,6,8,1]; i=3: current=1, list=[1,3,6,8]
(c) B1 [1, 3, 6, 8] ft from (b)
(c) Answer: [1, 3, 6, 8]
(d) M1 shifts the element at position j one place to the right
(d) A1 list[j + 1] <- list[j] (or equivalent correct logic; ignore minor syntax)
(d) Answer: list[j + 1] <- list[j]

Question 7

(a) B1 divide: the list is repeatedly split into two halves until each sub-list contains only one element (8 -> two lists of 4 -> four lists of 2 -> eight lists of 1)
(a) B1 merge: pairs of sorted sub-lists are combined by repeatedly comparing the front elements of each sub-list and taking the smaller first
(a) B1 merging continues, combining larger sorted sub-lists, until a single fully sorted list of all 8 elements remains
(a) Answer: Divide: the list is split in half repeatedly until each sub-list has one element. Merge: pairs of sorted sub-lists are combined by comparing their front elements, repeating until one sorted list of all 8 elements remains.
(b) B1 3
(b) Answer: 3
(c) B1 the list is halved repeatedly until sub-lists of size 1 remain, giving log2(n) levels of splitting/merging
(c) B1 at each level, merging all the sub-lists back together requires a total of (up to) n comparisons across that level
(c) B1 multiplying the number of levels (log n) by the work per level (n) gives an overall time complexity of O(n log n)
(c) Answer: There are log2(n) levels of splitting/merging, and each level does up to n comparisons in total; multiplying levels by work per level gives O(n log n).

Question 8

(a) M1 initialises low <- 0 and high <- LEN(titles) - 1
(a) M1 uses a loop (e.g. WHILE low ≤ high) that computes mid <- (low + high) DIV 2 each iteration
(a) M1 returns mid immediately if titles[mid] = newTitle
(a) M1 correctly narrows the range: low <- mid + 1 if titles[mid] < newTitle, else high <- mid - 1
(a) M1 when the loop ends without finding a match, returns low as the correct insertion position
(a) A1 overall algorithm is logically complete and correctly ordered (accept equivalent correct logic; ignore minor syntax errors)

(a) Answer:

FUNCTION FindInsertPosition(titles, newTitle) RETURNS INTEGER
  low <- 0
  high <- LEN(titles) - 1
  WHILE low <= high
    mid <- (low + high) DIV 2
    IF titles[mid] = newTitle THEN
      RETURN mid
    ELSE IF titles[mid] < newTitle THEN
      low <- mid + 1
    ELSE
      high <- mid - 1
    ENDIF
  ENDWHILE
  RETURN low
ENDFUNCTION

Question 9

(a) B1 O(n) cao
(a) B1 the single loop runs n times, performing one operation each time (oe)
(a) Answer: O(n): a single loop runs n times with one operation per iteration.
(b) B1 O(n²) cao
(b) B1 two nested loops, each running n times, give n x n = n² operations (oe)
(b) Answer: O(n²): two nested loops each of length n give n x n operations.
(c) B1 O(log n) cao
(c) B1 count is halved (DIV 2) each iteration, so the loop runs approximately log2(n) times (oe)
(c) Answer: O(log n): count is halved each iteration, so the loop runs about log2(n) times.
(d) B1 O(n log n) cao
(d) B1 the outer loop runs n times, and each time it performs a binary-search-style loop taking O(log n), giving n x log n operations (oe)
(d) Answer: O(n log n): the outer loop runs n times, and each time performs an O(log n) binary-search-style loop.

Question 10

(a) B1 Linear search: O(n)
(a) B1 Binary search: O(log n)
(a) B1 Bubble sort: O(n²)
(a) B1 Insertion sort: O(n²)
(a) B1 Merge sort: O(n log n)
(a) Answer: Linear search O(n); Binary search O(log n); Bubble sort O(n²); Insertion sort O(n²); Merge sort O(n log n).
(b) B1 bubble sort: in place, O(1) extra memory
(b) B1 insertion sort: in place, O(1) extra memory
(b) B1 merge sort: requires significant additional memory, O(n) extra memory (for the temporary arrays used when merging)
(b) Answer: Bubble sort and insertion sort both sort in place (O(1) extra memory); merge sort needs O(n) extra memory for its temporary merge arrays.
(c) B1 insertion sort
(c) B1 because insertion sort only has to shift the small number of out-of-place elements a short distance, so on a nearly-sorted list it performs close to O(n) comparisons, whereas bubble sort's structure typically still leads to more comparisons before it can detect the list is sorted (oe, allow reasonable justification about adaptiveness)
(c) Answer: Insertion sort, because it adapts well to nearly-sorted data, only needing to shift the few out-of-place elements, giving close to O(n) performance rather than the larger number of comparisons typical of bubble sort.

Question 11

(a) L1 (1-2): Basic, isolated points are made about searching and/or sorting algorithms, with little or no reference to time complexity or to the given scenario. The answer may simply name algorithms with no justification.
(a) L2 (3-4): Some relevant points are made about appropriate searching and sorting algorithms, with limited reference to time complexity (e.g. Big O notation used but not clearly applied to the scale of the data). Some link is made to the scenario (2,000,000 records, daily batch updates).
(a) L3 (5-6): A clear, well-justified discussion is given, correctly identifying appropriate searching and sorting algorithms, supported by accurate use of time complexity (Big O notation) applied specifically to the scale of the scenario (2,000,000 records) and the fact that the data is sorted and updated in daily batches.
(a) Answer: Best answers recommend binary search (O(log n)) for daily lookups and merge sort (O(n log n)) for the nightly re-sort, justified using Big O notation applied to n = 2,000,000.

Question 12

(a) M1 C(2) = 2 x C(1) + (2 - 1) = 2 x 0 + 1
(a) M1 C(4) = 2 x C(2) + (4 - 1) = 2 x 1 + 3
(a) A1 C(2) = 1 and C(4) = 5 cao
(a) Answer: C(2) = 1, C(4) = 5
(b) M1 C(8) = 2 x C(4) + (8 - 1) = 2 x 5 + 7
(b) A1 = 17 cso (answer given)
(b) Answer: C(8) = 17
(c) B1 yes; 17 is the same order of magnitude as n log2(n) = 8 x 3 = 24, consistent with O(n log n) growth (oe)
(c) Answer: Yes; 17 is the same order of magnitude as n log2(n) = 24, consistent with O(n log n) growth.

Algorithms: Complexity, Searching and Sorting - Worksheets, Questions and Revision