MskProdComputing
Back to the topic

The mark scheme starts on a new page, so you can print pages one and two for a student and keep the last page yourself. Everything prints in black on white whichever theme you are using.

A Level · 2.3.1

Algorithms and Big O Complexity

Section A: 10 multiple choice questions, 10 marks. Section B: 5 written questions, 25 marks. Total 35 marks.

Name

Class

Date

Mark  / 35

Section A

Circle the letter of the correct answer. One mark each.

  1. 1What is the time complexity of binary search?1
    1. AO(1)
    2. BO(n log n)
    3. CO(n)
    4. DO(log n)
  2. 2Which sorting algorithm has consistent O(n log n) performance in all cases?1
    1. AMerge sort
    2. BInsertion sort
    3. CQuicksort
    4. DBubble sort
  3. 3What is the space complexity of merge sort?1
    1. AO(1)
    2. BO(n)
    3. CO(log n)
    4. DO(n log n)
  4. 4Which data structure does breadth first search use?1
    1. AA binary tree
    2. BA stack
    3. CA hash table
    4. DA queue
  5. 5Why can Dijkstra's algorithm not handle negative edge weights?1
    1. AIt cannot store negative numbers
    2. BNegative weights are impossible in a graph
    3. CA visited node's distance is assumed final, which a negative edge could invalidate
    4. DThe queue would overflow
  6. 6In A star, what does f(n) = g(n) + h(n) represent?1
    1. AThe number of nodes visited
    2. BThe actual cost so far plus the estimated cost remaining
    3. CThe heuristic alone
    4. DThe total number of edges
  7. 7What makes a heuristic admissible?1
    1. AIt uses straight line distance only
    2. BIt is calculated in constant time
    3. CIt never overestimates the true remaining cost
    4. DIt always finds the answer quickly
  8. 8Which traversal of a binary search tree produces sorted output?1
    1. AIn order
    2. BPost order
    3. CBreadth first
    4. DPre order
  9. 9Why is bubble sort O(n squared)?1
    1. AIt makes up to n passes, each comparing up to n elements
    2. BIt halves the list n times
    3. CIt calls itself n times
    4. DIt stores n copies of the list
  10. 10An algorithm takes 1 second on 1000 items and 100 seconds on 10000 items. What is its likely complexity?1
    1. AO(n log n)
    2. BO(n squared)
    3. CO(n)
    4. DO(log n)

Section B

Answer in the space provided. The number of marks tells you how many separate points to make.

  1. 1ExplainExplain what Big O notation describes and why constants are ignored.3
  2. 2CompareCompare merge sort and quicksort in terms of time complexity and space complexity.5
  3. 3DescribeDescribe how Dijkstra's algorithm finds the shortest path between two nodes in a weighted graph.6
  4. 4ExplainExplain how the A star algorithm differs from Dijkstra's algorithm and why it is usually faster.5
  5. 5CompareA system stores 10 million records and must be searched frequently by a unique key. Compare linear search, binary search and a hash table for this purpose.6

Mark scheme

Section A

1D2A3B4D5C6B7C8A9A10B

Section B

1 Explain what Big O notation describes and why constants are ignored. 3

One mark for each of the following, to a maximum of 3.

  • It describes how resource use grows as the input size increases
  • It describes the worst case unless otherwise stated
  • Constants and lower order terms are ignored because only dominant growth matters at scale

Model answer. Big O notation describes how the resources an algorithm requires, usually time but also memory, grow as the size of the input increases, and unless stated otherwise it describes the worst case, giving an upper bound on the behaviour. Constants and lower order terms are discarded because they become insignificant as the input grows. An algorithm taking 3n squared plus 100n plus 5000 operations is written as O(n squared), because once n is large the squared term dominates completely and the difference between 3n squared and n squared is a fixed multiple that does not change the fundamental scaling behaviour. This matters because the purpose of Big O is to compare how algorithms behave as data grows, not to predict exact runtimes on a particular machine.

2 Compare merge sort and quicksort in terms of time complexity and space complexity. 5

One mark for each of the following, to a maximum of 5.

  • Merge sort is O(n log n) in all cases including the worst
  • Quicksort averages O(n log n) but degrades to O(n squared) in the worst case
  • The quicksort worst case occurs when the pivot is consistently the smallest or largest element
  • Merge sort requires O(n) additional space for the sub lists
  • Quicksort sorts largely in place using only O(log n) stack space

Model answer. Merge sort has time complexity O(n log n) in the best, average and worst cases alike, because it always divides the list exactly in half regardless of the data and always performs the same merging work. Quicksort has average time complexity O(n log n) and in practice usually outperforms merge sort because its constant factors are smaller, but its worst case is O(n squared). That worst case occurs when the chosen pivot is consistently the smallest or largest remaining element, so each partition removes only one item rather than roughly half, and it arises naturally if the first element is chosen as the pivot on data that is already sorted. Practical implementations avoid it by choosing the pivot as the median of three candidates or at random. Space is where the comparison reverses. Merge sort requires O(n) additional memory because the sub lists produced by the divide phase must be stored while merging, whereas quicksort partitions the array in place and needs only O(log n) stack space for its recursive calls. The choice therefore depends on priorities: merge sort when guaranteed performance is essential or when sorting data that does not fit in memory, quicksort when average speed matters most and memory is constrained.

3 Describe how Dijkstra's algorithm finds the shortest path between two nodes in a weighted graph. 6

One mark for each of the following, to a maximum of 6.

  • The source node distance is set to zero and all others to infinity
  • The unvisited node with the smallest known distance is selected as the current node
  • For each unvisited neighbour the distance through the current node is calculated
  • If that distance is smaller than the recorded distance it replaces it
  • The predecessor is recorded so the path can be reconstructed
  • The current node is marked visited and the process repeats until the destination is reached

Model answer. Dijkstra's algorithm begins by setting the distance to the source node as zero and the distance to every other node as infinity, with all nodes marked unvisited. It then repeatedly selects, from among the unvisited nodes, the one with the smallest recorded distance, and treats this as the current node. For each unvisited neighbour of the current node, it calculates the distance to that neighbour by travelling through the current node, which is the current node's distance plus the weight of the connecting edge. If this calculated distance is less than the distance already recorded for that neighbour, the recorded distance is replaced with the new smaller value and the current node is stored as that neighbour's predecessor. Once all neighbours have been considered, the current node is marked as visited and will not be examined again, because its distance is now known to be final. The process repeats, always choosing the unvisited node with the smallest distance, until the destination has been visited or no reachable unvisited node remains. The shortest path itself is then recovered by starting at the destination and following the chain of recorded predecessors back to the source, which yields the route in reverse.

4 Explain how the A star algorithm differs from Dijkstra's algorithm and why it is usually faster. 5

One mark for each of the following, to a maximum of 5.

  • A star adds a heuristic estimate of the remaining cost to the goal
  • Nodes are selected by the lowest value of f equals g plus h
  • Dijkstra explores outwards in all directions equally
  • A star prioritises nodes appearing to lead towards the goal, so it examines fewer nodes
  • It still finds the optimal path provided the heuristic never overestimates

Model answer. Dijkstra's algorithm always expands the unvisited node with the smallest distance from the source, which means it explores outwards from the start in every direction equally, discovering shortest paths to nodes that lie entirely away from the destination before it happens to reach the destination itself. A star modifies the selection rule by adding a heuristic estimate of the remaining cost from each node to the goal, so it chooses the node with the lowest value of f, where f equals g plus h, g being the actual cost accumulated from the start and h being the estimated cost still to travel. Because a node lying in the direction of the goal receives a low h value, it is selected in preference to a node that is equally close to the start but heading away, so the search is directed rather than uniform and typically examines a small fraction of the nodes that Dijkstra would. Crucially, A star still guarantees the optimal path provided the heuristic is admissible, meaning it never overestimates the true remaining cost, since underestimating simply means the algorithm may explore a few extra nodes rather than committing to a suboptimal route. Straight line distance is the standard admissible heuristic for geographic pathfinding, since no actual route can be shorter than a straight line. Dijkstra can be seen as the special case of A star where h is zero everywhere.

5 A system stores 10 million records and must be searched frequently by a unique key. Compare linear search, binary search and a hash table for this purpose. 6

One mark for each of the following, to a maximum of 6.

  • Linear search is O(n) and would examine up to 10 million records per search
  • Linear search requires no ordering but is far too slow at this scale
  • Binary search is O(log n), needing about 24 comparisons
  • Binary search requires the data to be kept sorted, which costs time on insertion
  • A hash table gives average O(1) lookup by calculating the position from the key
  • Recommends the hash table, noting it does not support ordered or range queries

Model answer. Linear search has time complexity O(n), so on 10 million records it would examine on average five million and at worst all ten million entries for every single query. It has the advantage of requiring no ordering or preparation at all, but at this scale and with frequent searching it is completely impractical. Binary search has complexity O(log n), which reduces the work to about 24 comparisons for ten million records, an improvement of roughly six orders of magnitude. Its precondition is that the data must be kept in sorted order, which means either sorting once at O(n log n) if the data is static, or paying an insertion cost to maintain the ordering as records are added, and inserting into a sorted array requires shifting subsequent elements. A hash table offers average O(1) lookup, because the hash function calculates the storage index directly from the key so no searching of any kind is performed, and the time taken does not increase as the number of records grows. Given that the search is by a unique key and is performed frequently, the hash table is the strongest choice, and it should be sized so the load factor stays low enough that collisions remain rare. The one caveat is that a hash table imposes no useful ordering on the data, so if the system also needs to retrieve records in key order or answer range queries such as all keys between two values, a balanced binary search tree giving O(log n) for both lookup and ordered traversal would be the better overall structure.