Algorithms — OCR A-Level Computer Science
Algorithms explained
Algorithms covers 6 specification points, including (a) Analysis and design of algorithms for a… and (b) The suitability of different algorithms….
Read the full explanation
Open a point below for its explanation and revision guidance.
(a) Analysis and design of algorithms for a given situation.
This criterion covers analysing and designing algorithms for a given situation. Analysis means identifying from the scenario the inputs, outputs, constraints such as time, memory or accuracy, and the processing needed to link them. Design means proposing an algorithm that meets those requirements using sequence, selection and iteration, shown in pseudocode or a flowchart. Keep it specific: refer to named data, conditions and outcomes rather than writing a generic procedure. For example, a booking system must check available seats before confirming and define a response when none remain. Justify each design choice against the requirements, such as choosing a sorted search for a large dataset queried often.
(b) The suitability of different algorithms for a given task and data set, in terms of execution time and space.
This criterion asks you to judge which algorithm best fits a given task and data set, weighing execution time (how the number of steps grows with input size) and space (the extra memory needed while the algorithm runs). Start by reading the task and the data: is the list sorted, does it fit in memory, and is an exact answer required? For example, a linear search suits ten unsorted names, whereas a binary search is unsuitable for unsorted data unless the data is sorted first. Next, compare the candidate algorithms on both measures, noting that a faster algorithm may use more memory, such as a hash table lookup compared with a sequential scan. Finally, justify your choice by linking each strength and weakness to the specific task and data, rather than making a general claim that one algorithm is best.
(c) Measures and methods to determine the efficiency of different algorithms, Big O notation (constant, linear, polynomial, exponential and logarithmic complexity).
This criterion covers the measures and methods used to determine algorithm efficiency, and Big O notation as the standard way to describe how cost grows with input size n. Measures include counting basic operations such as comparisons and recording the memory used, while timing an algorithm is a practical but hardware-dependent check. Big O drops constant factors and lower-order terms, so 3n + 5 is O(n). Constant O(1) does not change with n, such as reading an array element by index. Logarithmic O(log n) halves the remaining problem each step, as binary search does; 1 000 000 items need about 20 comparisons because 2²⁰ = 1 048 576. Linear O(n) doubles the work when n doubles, as in a linear search. Polynomial O(nᵏ) for a fixed k, such as O(n²) for a nested loop comparing every pair, multiplies the work by 2ᵏ when n doubles.
(d) Comparison of the complexity of algorithms.
This statement asks you to compare algorithms by their complexity: how resource use grows as the input grows. Complexity has two measures: time complexity, the number of steps an algorithm takes, and space complexity, the amount of memory it needs. Express both with Big O notation, which describes the upper bound on growth as input size n increases. For example, linear search on n items is O(n) in the worst case, while binary search on sorted data is O(log n), so binary search is preferable for large n. Compare how each function grows rather than timing one run on one machine. Nested loops over n items give O(n²), which grows far faster than O(n).
(e) Algorithms for the main data structures, (stacks, queues, trees, linked lists, depth-first (post-order) and breadth-first traversal of trees).
This statement requires algorithms for stacks, queues, trees, linked lists, post-order depth-first traversal and breadth-first traversal. A stack is last-in, first-out: push adds to the top and pop removes from the top. A queue is first-in, first-out: enqueue adds at the rear and dequeue removes from the front. For linked lists, insertion updates pointers so the new node points onward and its predecessor points to it. Depth-first post-order traversal visits the left subtree, then the right subtree, then the root. Breadth-first traversal visits nodes level by level, using a queue to hold nodes awaiting visit. Trace each algorithm on a small tree, recording the output order.
(f) Standard algorithms (bubble sort, insertion sort, merge sort, quick sort, Dijkstra’s shortest path algorithm, A* algorithm, binary search and linear search).
Know eight standard algorithms and what each one does. Bubble sort repeatedly compares neighbouring items and swaps out-of-order pairs, so large values move to the end. Insertion sort builds a sorted section by inserting each item into its correct place. Merge sort splits a list into halves, sorts them and merges the results. Quick sort partitions data around a chosen pivot and sorts each part. Dijkstra’s shortest path algorithm finds the lowest-cost route through a weighted graph with non-negative edges. A* adds a heuristic estimate of remaining distance to guide its search. Binary search halves a sorted list to find a target, whereas linear search checks each item in turn.
Your focus
- Identify the inputs, outputs and constraints in a given scenario.
- Select or design an algorithm that meets every stated requirement of the scenario.
- Justify an algorithm design choice by reference to efficiency, accuracy or data size.
Show all 18 objectives
- Select an appropriate algorithm for a given task and data set, and justify the choice.
- Compare two algorithms in terms of execution time and space.
- Identify preconditions that make an algorithm unsuitable for particular data.
- Determine the Big O class of a simple algorithm by counting its dominant operations.
- Classify constant, logarithmic, linear, polynomial and exponential growth from a description or table of values.
- Explain how doubling the input size changes the work done for a given complexity class.
- Classify the time complexity of a given algorithm using Big O notation.
- Compare two algorithms by stating which grows more slowly as n increases.
- Explain why a single timed run is not a valid basis for comparing algorithm complexity.
- Trace push and pop operations on a stack and record the stack contents after each step.
- Produce the post-order and breadth-first sequences for a given tree.
- Write the pointer changes needed to insert a node into a linked list.
- Trace bubble sort and insertion sort on a short list, recording each comparison and swap.
- Explain how merge sort and quick sort divide the problem and then combine or partition the results.
- Identify the preconditions of binary search, linear search, Dijkstra’s algorithm and A*.
Algorithms exam tips
Marking Points
- Identifies inputs, outputs and constraints from the stated scenario before proposing any algorithm.
- Proposes an algorithm that meets every requirement in the scenario, including handling of edge cases.
- Uses sequence, selection and iteration appropriately within a clear, ordered structure.
- Expresses the design in pseudocode or a flowchart that a programmer could implement without guessing.
- Justifies design choices by linking them to efficiency, accuracy or data-size requirements.
- Refers to named data, conditions and outcomes from the scenario rather than generic steps.
- Identifies the key features of the given task and data set, such as sorted order, size and whether an exact answer is needed, before choosing an algorithm.
- Evaluates each candidate algorithm for execution time by describing how its number of steps grows with input size.
- Evaluates each candidate algorithm for space by stating the extra memory it needs while running.
- Recognises that a precondition, such as sorted data, can make an algorithm unsuitable for the given data set.
- Justifies the final choice by linking the trade-offs between time and space to the specific task and data set.
- Identifies the basic operation whose count determines the cost of an algorithm.
- Explains that Big O describes growth rate for large n and drops constant factors and lower-order terms.
- Classifies growth as constant, logarithmic, linear, polynomial or exponential using correct Big O notation.
- Explains how doubling n changes the work for a given class, such as the work quadrupling for O(n²).
- Notes that empirical timing depends on hardware and is therefore less reliable than counting operations.
- States whether the comparison concerns time complexity, space complexity or both, rather than only running time on one machine.
- Expresses the growth of each algorithm using Big O notation, such as O(n) or O(log n).
- Compares the functions for the same input size n and states which algorithm scales better as n grows.
- Explains that constant factors and lower-order terms are ignored when classifying growth.
- Justifies the conclusion with growth rates, for example noting that O(n²) overtakes O(n) as n becomes large.
- Describes push and pop on a stack, stating that the last item added is the first item removed.
- Describes enqueue and dequeue on a queue, stating that the first item added is the first item removed.
- Explains linked list insertion by updating pointers in the correct order so that no nodes are lost.
- Gives the post-order sequence as left subtree, right subtree, then root, applied to a stated tree.
- States that breadth-first traversal processes nodes level by level and uses a queue to hold nodes awaiting visit.
- States that bubble sort compares adjacent items and swaps them when they are out of order, so the largest unsorted value reaches the end after each pass.
- Describes insertion sort as building a sorted section one item at a time by inserting each item into its correct position.
- Explains merge sort as repeatedly dividing the list until single items remain, then merging sorted sublists.
- Explains quick sort as choosing a pivot and partitioning values either side of it before sorting each part.
- Identifies that Dijkstra’s algorithm finds shortest paths from a start node in a weighted graph with non-negative edge weights.
- Explains that A* uses a heuristic estimate of remaining cost to decide which node to explore next.
- Distinguishes binary search, which requires sorted data and halves the search interval, from linear search, which checks items in sequence.
Examiner Tips
- 💡Underline the inputs, outputs and constraints in the scenario before looking at the options.
- 💡When comparing designs, check each one against every stated requirement, not just the main one.
- 💡Prefer the option that handles the stated edge case or constraint explicitly over one that only works for typical data.
- 💡Begin by listing the key features of the task and data, such as sorted order, size and whether the answer must be exact.
- 💡Compare at least two candidate algorithms on both execution time and space, giving one clear point for each measure.
- 💡Finish with a justification that names the trade-off you accept, for example extra memory in exchange for faster lookups.
- 💡Count the basic operations in each loop and multiply nested loop counts to find the dominant term.
- 💡Learn the five classes in order of growth, from constant through logarithmic and linear to polynomial and exponential.
- 💡Test a claim by considering what happens to the work when n doubles, then state the class with a reason.
- 💡Name the resource first: state whether you are comparing time or space before giving any classification.
- 💡Use a concrete pair such as linear search and binary search to show the difference in growth, then state the conclusion.
- 💡When a question gives code, identify the dominant loop structure, state its Big O class and give a brief reason.
- 💡Draw the tree and label each node before tracing, so every visited node is recorded in the correct order.
- 💡For traversals, write the output sequence as a list and check each entry against the visiting rule.
- 💡For linked lists, sketch the pointer states before and after the change and mark which pointer is altered first.
- 💡Practise tracing each algorithm by hand on a list of five to eight values, recording the list after each pass or step.
- 💡Memorise the precondition for each algorithm, such as sorted data for binary search and non-negative edge weights for Dijkstra’s algorithm.
- 💡When answering, name the algorithm, state its key step and any prerequisite, then give a short worked example to show understanding.
Common Mistakes
- Writes a generic algorithm that ignores the stated situation; tie every step to the scenario's data and outcomes.
- Omits the analysis stage and moves straight to a solution; state inputs, outputs and constraints first.
- Handles only the normal case and leaves out empty or invalid inputs; add a defined response for each.
- Presents an algorithm without justification; explain why the chosen approach suits the stated constraints.
- Declares one algorithm the best overall without reference to the given task and data set; correct this by stating which conditions favour each algorithm.
- Considers only execution time and ignores space; correct this by weighing both measures for every candidate.
- Applies binary search to unsorted data without noting the need to sort it first; correct this by checking preconditions before choosing.
- Writes exponents at baseline height, such as n squared with no raised figure; correct this by using raised Unicode exponents.
- Keeps constant factors and lower-order terms in the final answer, giving 3n + 5 rather than O(n); correct this by dropping them.
- Treats logarithmic growth as linear because both increase with n; correct this by noting that each step halves the remaining problem.
- Compares algorithms using a single timed run, which depends on hardware; correct this by comparing growth rates as n increases.
- Confuses time complexity with space complexity; correct this by stating which resource each classification describes.
- Reverses the ordering by claiming O(n²) is more efficient than O(n); correct this by recognising that a faster-growing function is less efficient for large n.
- Mixes up stack and queue order by describing a queue as last-in, first-out; correct this by stating first-in, first-out for queues.
- Places the root first in a post-order traversal, which produces pre-order instead; correct this by visiting the root after both subtrees.
- Overwrites a predecessor's pointer before saving the link to the rest of the list, losing nodes; correct this by setting the new node's pointer first.
- Uses a stack rather than a queue for breadth-first traversal, which produces depth-first order; correct this by holding waiting nodes in a queue.
- Confuses bubble sort with insertion sort by describing a single insertion into a sorted section; correct it by describing repeated adjacent comparisons and swaps.
- Claims binary search works on unsorted data; correct it by stating that the list must be sorted before the search begins.
- Describes Dijkstra’s algorithm as handling negative edge weights; correct it by stating that the edge weights must be non-negative.
- Treats A* as always faster than every other method; correct it by explaining that the quality of the heuristic affects how many nodes are explored.