Algorithms — A-Level Computer Science Study Guide

For: A-Level Computer Science candidates sitting A-Level Computer Science.

Covers: Pseudocode and flowcharts, bubble and insertion sort, linear and binary search, time complexity intuition, and manual algorithm tracing as specified in the A-Level Computer Science syllabus.

You should already know: Basic programming concepts; one of Python / Java / VB.

A note on the practice questions: All worked questions in the "Practice Questions" section below are original problems written by us in the A-Level Computer Science style for educational use. They are not reproductions of past Cambridge International examination papers and may differ in wording, numerical values, or context. Use them to practise the technique; cross-check with official Cambridge mark schemes for grading conventions.

1. What Is Algorithms?

An algorithm is an unambiguous, finite sequence of step-by-step instructions designed to solve a specific problem or complete a defined task, with a clear end state and no ambiguous steps. Common synonyms include computational procedure, routine, or method. In the A-Level Computer Science syllabus, algorithms make up 10-15% of marks across both theory and practical papers, with questions testing your ability to design, analyze, trace, and implement core algorithm types.

2. Pseudocode and flowcharts

Pseudocode and flowcharts are the two standard language-agnostic methods for representing algorithms in A-Level Computer Science exams, so you are expected to read, interpret, and write both.

• Pseudocode: A plain-text representation of algorithm logic that follows loose, widely agreed structural conventions (no strict programming language syntax). A-Level uses a standard pseudocode format with explicit variable declaration, selection (IF/ELSE), iteration (FOR/WHILE loops), and subroutine notation.
• Flowcharts: A graphical representation of algorithm flow using 5 core standard symbols: oval for start/end, rectangle for processing steps, diamond for yes/no decision points, parallelogram for input/output, and directional arrows for control flow.

Worked Example

Problem: Design an algorithm to calculate the sum of all even numbers between 1 and a given positive integer N.

A-Level-standard Pseudocode

FUNCTION SumEvenNumbers(N : INTEGER) RETURNS INTEGER
 DECLARE sum, i : INTEGER
 sum = 0
 FOR i = 1 TO N
 IF i MOD 2 = 0 THEN
 sum = sum + i
 ENDIF
 NEXT i
 RETURN sum
ENDFUNCTION

Equivalent Flow Structure

1. Start (oval) → Input N (parallelogram) → Initialize sum=0 and i=1 (rectangle)
2. Decision (diamond): Is i > N? If Yes, output sum (parallelogram) → End (oval)
3. If No: Decision: Is i MOD 2 = 0? If Yes, add i to sum (rectangle)
4. Increment i by 1 (rectangle) → Loop back to the first decision point

Exam tip: Examiners deduct marks for non-standard flowchart symbols or unlabelled decision arrows, so always label every diamond output with "Yes" or "No" matching the stated condition.

3. Sorting algorithms — bubble, insertion

Sorting algorithms rearrange a list of elements into a defined order (usually ascending or descending numerical/lexicographical order). You are required to know the logic, pseudocode, and performance of two core comparison sorts for A-Level Computer Science.

Bubble Sort

Bubble sort works by repeatedly stepping through the unsorted list, comparing adjacent pairs of elements, and swapping them if they are in the wrong order. It repeats passes through the list until no swaps are needed, indicating the list is fully sorted. An optional optimization adds a swapped flag to exit early if no swaps occur in a pass (meaning the list is already sorted).

Worked Example (ascending sort of [5, 2, 7, 1, 3])

1. Pass 1: Swap 5&2 → [2,5,7,1,3], swap 7&1 → [2,5,1,7,3], swap 7&3 → [2,5,1,3,7] (3 swaps total)
2. Pass 2: Swap 5&1 → [2,1,5,3,7], swap 5&3 → [2,1,3,5,7] (2 swaps total)
3. Pass 3: Swap 2&1 → [1,2,3,5,7] (1 swap total)
4. Pass 4: No swaps → exit, list sorted

Insertion Sort

Insertion sort builds the final sorted list one element at a time: it splits the list into a sorted left portion and unsorted right portion, takes one element from the unsorted portion, and inserts it into its correct position in the sorted portion. It is generally more efficient than bubble sort for small or nearly sorted lists.

Worked Example (same input list [5,2,7,1,3])

1. Sorted portion = [5], insert 2 → [2,5]
2. Insert 7 into sorted portion → [2,5,7]
3. Insert 1 into sorted portion → [1,2,5,7]
4. Insert 3 into sorted portion → [1,2,3,5,7] → list sorted

4. Searching algorithms — linear, binary

Searching algorithms locate the position of a target value in a list, or confirm the target is not present. You are required to know two core search algorithms for A-Level Computer Science.

Linear (Sequential) Search

Linear search checks every element in the list in order, one at a time, until the target is found or the end of the list is reached. It works on both sorted and unsorted lists, but is inefficient for large datasets.

Worked Example (search for target 9 in [3,7,2,9,5])

1. Check index 0 (3) → no match
2. Check index 1 (7) → no match
3. Check index 2 (2) → no match
4. Check index 3 (9) → match, return index 3

Binary Search

Binary search only works on pre-sorted lists and uses a divide-and-conquer approach: it repeatedly splits the search interval in half, compares the target to the middle element of the interval, and eliminates the half of the list that cannot contain the target. It is significantly faster than linear search for large sorted datasets.

Worked Example (search for target 7 in sorted list [2,3,5,7,9])

1. Full list interval: start=0, end=4. Mid index = 2, value =5. 5 <7 → search right half (start=3, end=4)
2. Mid index = 3, value=7 → match, return index 3

Exam tip: Examiners frequently ask for the prerequisite for binary search as a 1-mark question, so always state that the list must be sorted before describing binary search logic.

5. Time complexity intuition

Time complexity measures how the runtime of an algorithm scales as the size of its input (denoted $n$) increases. For A-Level Computer Science, you only need to understand relative performance using Big O notation, which describes the worst-case (maximum possible) runtime of an algorithm for a given input size.

• Constant time O(1): Runtime does not change with input size (e.g. accessing an array element by its index)
• Logarithmic time O($\log n$): Runtime grows very slowly as $n$ increases (e.g. binary search, which halves the search space every step)
• Linear time O($n$): Runtime grows proportionally to $n$ (e.g. linear search, worst case you check all $n$ elements)
• Quadratic time O($n^2$): Runtime grows with the square of $n$ (e.g. bubble and insertion sort, worst case you make $n$ passes each with $n$ comparisons)

For context, if $n=1000$:

• O($\log n$) = ~10 steps, O($n$) = 1000 steps, O($n^2$) = 1,000,000 steps.

Exam tip: You do not need to calculate formal Big O values for A-Level Computer Science, but you will be asked to compare the efficiency of the four core algorithms for large input sizes.

6. Tracing algorithms by hand

Tracing is the process of manually following the execution of an algorithm step by step, recording changes to variable values, outputs, and control flow. It is tested in every A-Level Computer Science theory paper, almost exclusively using a trace table format, where each column represents a variable or output, and each row represents one execution step.

Worked Example

Trace the SumEvenNumbers function from Section 2 with input $N=4$:

Exam tip: Always fill one row per execution step even if variable values do not change. Examiners award marks per correct row, so skipping steps will lose marks even if your final output is correct.

7. Common Pitfalls (and how to avoid them)

• Pitfall 1: Using custom flowchart symbols or failing to label decision arrows. Why students make this mistake: They forget A-Level's standard symbol set in exam conditions. Correct move: Memorize the 5 core flowchart symbols, and label every diamond decision output with explicit "Yes" or "No" labels matching the condition.
• Pitfall 2: Writing binary search logic for an unsorted list. Why students make this mistake: They rush through questions and skip the prerequisite check. Correct move: The first line of any binary search answer must state that the input list must be sorted; if not, use linear search or sort the list first.
• Pitfall 3: Omitting the early exit optimization for bubble sort. Why students make this mistake: They only memorize the basic unoptimized version. Correct move: Always include a swapped flag in bubble sort pseudocode that breaks the loop early if no swaps occur in a pass; this is required for full marks in most questions.
• Pitfall 4: Confusing worst and best case time complexity. Why students make this mistake: They mix up performance scenarios. Correct move: When asked about efficiency, always specify worst case first (the default for A-Level Computer Science questions), e.g. "Bubble sort has a worst-case time complexity of O($n^2$), and a best case of O($n$) when the list is already sorted with the early exit optimization".
• Pitfall 5: Skipping steps in trace tables. Why students make this mistake: They assume intermediate steps are not marked. Correct move: Fill every row of the trace table, even if variable values do not change, as marks are awarded per step.

8. Practice Questions (A-Level Computer Science Style)

Question 1

(a) Draw a flowchart for an algorithm that takes a list of 10 integers as input, counts how many are negative, and outputs the count. [4 marks] (b) Write equivalent A-Level-standard pseudocode for the same algorithm. [3 marks]

Worked Solution

(a) Full marks awarded for:

1. Correct start/end symbols, input step for the 10-integer array, and initialization of count=0 and i=0 (1 mark)
2. First decision point i < 10 with Yes/No labels (1 mark)
3. Second decision point Arr[i] < 0 that increments count if true (1 mark)
4. Correct increment of i and control flow back to the first decision, plus output of count when loop exits (1 mark)

(b) Full marks awarded for the following pseudocode:

DECLARE Arr : ARRAY[0:9] OF INTEGER
DECLARE count, i : INTEGER
count = 0
FOR i = 0 TO 9
 INPUT Arr[i]
 IF Arr[i] < 0 THEN
 count = count + 1
 ENDIF
NEXT i
OUTPUT count

1 mark for correct variable declarations, 1 mark for correct loop and input logic, 1 mark for correct selection and output.

Question 2

A list of integers [9, 4, 6, 2, 7, 1] is sorted in ascending order using insertion sort. Show the full state of the list after each element is inserted into the sorted portion. [4 marks]

Worked Solution

1 mark per correct intermediate state:

1. After inserting 4: [4, 9, 6, 2, 7, 1]
2. After inserting 6: [4, 6, 9, 2, 7, 1]
3. After inserting 2: [2, 4, 6, 9, 7, 1]
4. After inserting 7: [2, 4, 6, 7, 9, 1]
5. After inserting 1: [1, 2, 4, 6, 7, 9] Full marks awarded for all 5 states listed correctly.

Question 3

A sorted list of 128 integers is searched for a target value. (a) State the maximum number of comparisons needed for a linear search. [1 mark] (b) State the maximum number of comparisons needed for a binary search. [1 mark] (c) Explain why binary search is not suitable for an unsorted list. [2 marks]

Worked Solution

(a) 128 (worst case the target is the last element or not present, so all 128 elements are checked) (b) 7 (since $2^7=128$, each comparison halves the search space, so maximum 7 steps are needed) (c) Binary search uses the sorted order of the list to eliminate half the search space with every comparison. If the list is unsorted, there is no way to confirm if the target is in the left or right half of the midpoint, so the divide-and-conquer logic fails. (1 mark for linking to divide-and-conquer logic, 1 mark for explaining the ambiguity of unsorted lists)

9. Quick Reference Cheatsheet

10. What's Next

The algorithm fundamentals covered in this guide are the foundation for all later A-Level Computer Science topics, including recursion, advanced sorting algorithms (merge sort, quicksort), data structure operations (linked lists, binary trees, graphs), and algorithm design paradigms like divide-and-conquer and dynamic programming. You will also apply tracing and time complexity analysis skills in your practical programming papers to debug and optimize code for assessment.

If you have any questions about algorithm design, tracing, or time complexity that are not covered in this guide, you can ask Ollie at any time for step-by-step explanations, extra practice questions, or personalized feedback on your work. Head to the homepage to access more A-Level Computer Science study materials, past paper walkthroughs, and AI-powered tutoring support.

Aligned with the Cambridge International AS & A Level Computer Science 9618 syllabus. OwlsAi is not affiliated with Cambridge Assessment International Education.