Why is "Applying a binary search to unsorted data and expecting a correct result." a common mistake in Algorithms?

Why it happens: Students remember binary search is 'faster' but forget that the halving logic only works when the data is in order. How to avoid it: Always state and check the precondition: a binary search requires SORTED data. On unsorted data, use a linear search or sort the data first. Source: Examiner reports note that the sorted-data condition is the most frequently omitted point in binary-search questions.

Why is "Writing a search loop that runs off the end of the data — e.g. dereferencing a node after the pointer has become 0, or letting Low exceed High." a common mistake in Algorithms?

Why it happens: The stopping condition is placed after the access, or the 'not found' case is forgotten. How to avoid it: Put the boundary test in the loop condition: `WHILE Current <> 0 DO` for a linked list and `WHILE Low <= High DO` for a binary search, and always return 0 (not found) after the loop.

Why is "Stating that insertion sort (or bubble sort) is always O(n^2) regardless of the data." a common mistake in Algorithms?

Why it happens: Students memorise the worst case and ignore how performance depends on the initial order. How to avoid it: Remember these sorts are adaptive: on (nearly) sorted data the inner loop barely runs, giving a best case of ~O(n). Performance depends on both initial order and number of items.

Why is "Confusing where a stack and a queue add and remove items (e.g. removing from the front of a stack)." a common mistake in Algorithms?

Why it happens: LIFO and FIFO are easily mixed up, especially under exam pressure. How to avoid it: Stack = LIFO: PUSH and POP at the SAME end (Top). Queue = FIFO: add at the REAR, remove from the FRONT (two pointers).

Why is "When traversing a linked list, forgetting to advance to the next node, causing an infinite loop." a common mistake in Algorithms?

Why it happens: Students check `Data[Current]` but never update `Current ← Pointer[Current]`. How to avoid it: Inside the traversal loop, always follow the pointer to the next node before the next iteration: `Current ← Pointer[Current]`.

Why is "Mixing up the Big O orders — e.g. calling binary search O(n) or array indexing O(n)." a common mistake in Algorithms?

Why it happens: The orders are learned as a list without connecting them to what the algorithm actually does. How to avoid it: Link each order to a behaviour: direct index access = O(1); halving the range = O(log n); checking each item = O(n); nested loops = O(n^2).

Cambridge International A Levels Computer Science (9618)

Algorithms

Q: Why is "Stating that insertion sort (or bubble sort) is always O(n^2) regardless of the data." a common mistake in Algorithms?

Why it happens: Students memorise the worst case and ignore how performance depends on the initial order. How to avoid it: Remember these sorts are adaptive: on (nearly) sorted data the inner loop barely runs, giving a best case of ~O(n). Performance depends on both initial order and number of items.

Q: Why is "Confusing where a stack and a queue add and remove items (e.g. removing from the front of a stack)." a common mistake in Algorithms?

Why it happens: LIFO and FIFO are easily mixed up, especially under exam pressure. How to avoid it: Stack = LIFO: PUSH and POP at the SAME end (Top). Queue = FIFO: add at the REAR, remove from the FRONT (two pointers).

Q: Why is "When traversing a linked list, forgetting to advance to the next node, causing an infinite loop." a common mistake in Algorithms?

Why it happens: Students check `Data[Current]` but never update `Current ← Pointer[Current]`. How to avoid it: Inside the traversal loop, always follow the pointer to the next node before the next iteration: `Current ← Pointer[Current]`.

Q: Why is "Mixing up the Big O orders — e.g. calling binary search O(n) or array indexing O(n)." a common mistake in Algorithms?

Why it happens: The orders are learned as a list without connecting them to what the algorithm actually does. How to avoid it: Link each order to a behaviour: direct index access = O(1); halving the range = O(log n); checking each item = O(n); nested loops = O(n^2).

0% Complete

Detailed Study Notes

Detailed notes on Computational thinking and Problem-Solving for Cambridge International A Levels Computer Science, covering key concepts, explanations, examples, and exam-focused revision points.

Algorithms (A Level) — Cambridge AS & A Level Computer Science 9618 Study Notes (2027-2029)

Searching (linear vs binary), sorting (bubble vs insertion), abstract data types (linked list, stack, queue, binary tree, dictionary, graph), how one ADT can be built from another, and comparing algorithms with Big O notation for time and space. Everything is written in Cambridge pseudocode and traced by hand — keep your data sets small. No calculator is allowed.

At a glance

Linear search checks each item in turn → works on unsorted data → $O(n)$ .
Binary search halves the range each step → needs sorted data → $O(\log n)$ .
Bubble sort and insertion sort are both $O(n^2)$ worst case, but ~ $O(n)$ on (nearly) sorted data.
Performance depends on the initial order of the data and the number of items.
An ADT describes data + operations by what it does, not how it is stored (stack, queue, linked list, binary tree, dictionary, graph).
Stack = LIFO (one end, Top); queue = FIFO (rear in, front out).
A graph is an ADT for many-to-many connections — describe and justify it, but you do not code it in 9618.
ADTs can be implemented from other types — a stack/queue/dictionary from an array; a linked list from arrays + pointers; a binary tree from nodes or arrays.
Big O describes how time AND space grow with input size $n$ : $O(1)$ , $O(\log n)$ , $O(n)$ , $O(n \log n)$ , $O(n^2)$ .

What you’ll learn

Mapped to the Cambridge International A Level 9618 syllabus (2027-2029).

19.1 — Write algorithms to implement a linear search and a binary search, and state the conditions required for a binary search.
19.1 — Describe how the performance of a linear and a binary search varies with the number of items in a list.
19.1 — Write algorithms to implement an insertion sort and a bubble sort, and describe how their performance depends on the initial order of the data and the number of items.
19.1 — Write algorithms to find an item in a linked list and a binary tree, and to insert and delete items in a stack, queue, linked list and binary tree.
19.1 — Show understanding that a graph is an abstract data type (ADT) and justify the use of a graph.
19.1 — Show understanding that an ADT can be implemented from another ADT or from built-in types (stack, queue, linked list, dictionary, binary tree).
19.1 — Compare algorithms using suitable criteria, including Big O notation for time complexity and space complexity.

Searching: linear vs binary

Check each item ( $O(n)$ , unsorted) or halve the range each step ( $O(\log n)$ , sorted).

A search algorithm finds the position of a target value in a list (or reports that it is absent).

Linear search checks each element in turn, from first to last:

FUNCTION LinearSearch(Target : INTEGER) RETURNS INTEGER
  DECLARE i : INTEGER
  FOR i ← 1 TO n
    IF A[i] = Target THEN
      RETURN i
    ENDIF
  NEXT i
  RETURN 0       // not found
ENDFUNCTION

It works on unsorted data and, in the worst case, must compare every one of the $n$ items → time complexity $O(n)$ .

Binary search is much faster but requires the data to be sorted. It repeatedly looks at the middle item and discards the half that cannot contain the target:

FUNCTION BinarySearch(Target : INTEGER) RETURNS INTEGER
  DECLARE Low, High, Mid : INTEGER
  Low ← 1
  High ← n
  WHILE Low <= High DO
    Mid ← (Low + High) DIV 2
    IF A[Mid] = Target THEN
      RETURN Mid
    ELSE
      IF A[Mid] < Target THEN
        Low ← Mid + 1
      ELSE
        High ← Mid - 1
      ENDIF
    ENDIF
  ENDWHILE
  RETURN 0       // not found
ENDFUNCTION

How performance varies with the number of items: for a linear search, doubling the data roughly doubles the worst-case work ( $O(n)$ ). For a binary search, doubling the data adds just one extra comparison ( $O(\log n)$ ). So for 1000 items, a linear search may need up to 1000 comparisons but a binary search needs only about 10.

Linear search: check each item; unsorted data; $O(n)$ .
Binary search: check the middle, discard half; SORTED data; $O(\log n)$ .
Mid ← (Low + High) DIV 2; loop ends when Low > High (not found).
Doubling n: +1 comparison for binary, ×2 work for linear.

See the full worked example for algorithms →

Sorting: bubble vs insertion

Both $O(n^2)$ worst case; both ~ $O(n)$ best case on nearly-sorted data.

A sort rearranges a list into order (e.g. ascending). 9618 requires two simple sorts.

Bubble sort repeatedly passes through the list, comparing adjacent items and swapping any that are out of order, so the largest unsorted value 'bubbles' to the end each pass:

PROCEDURE BubbleSort()
  DECLARE i, j, Temp : INTEGER
  FOR i ← 1 TO n - 1
    FOR j ← 1 TO n - i
      IF A[j] > A[j + 1] THEN
        Temp ← A[j]
        A[j] ← A[j + 1]
        A[j + 1] ← Temp
      ENDIF
    NEXT j
  NEXT i
ENDPROCEDURE

Insertion sort builds a sorted section at the left by taking each next item (Key) and inserting it into its correct place, shifting larger items right:

PROCEDURE InsertionSort()
  DECLARE i, j, Key : INTEGER
  FOR i ← 2 TO n
    Key ← A[i]
    j ← i - 1
    WHILE j >= 1 AND A[j] > Key DO
      A[j + 1] ← A[j]
      j ← j - 1
    ENDWHILE
    A[j + 1] ← Key
  NEXT i
ENDPROCEDURE

How performance depends on initial order and size:

	Best case	Worst case
Bubble sort	~ $O(n)$ (one clean pass, with a swap-flag check)	$O(n^2)$
Insertion sort	$O(n)$ (data nearly sorted)	$O(n^2)$ (reverse order)

Both are adaptive: on data that is already (nearly) sorted, the inner loop barely runs, so they are efficient for small or nearly-sorted lists. The more items there are, and the further the data is from sorted, the more work is done — so performance depends on both the initial order and the number of items.

Bubble sort: swap adjacent out-of-order items; largest bubbles to the end.
Insertion sort: insert each item into the growing sorted section.
Both worst case $O(n^2)$ ; both best case ~ $O(n)$ on (nearly) sorted data.
Performance depends on initial order AND number of items.

See the full worked example for algorithms →

Linear ADTs: linked list, stack, queue

A linked list chains nodes by pointers; a stack is LIFO; a queue is FIFO.

An abstract data type (ADT) is a collection of data plus a set of operations, defined by what it does rather than how it is stored.

Linked list — each node holds a data value and a pointer to the next node. A Start pointer marks the first node; a null pointer (0) marks the end. To find an item you follow the chain:

FUNCTION FindNode(Target : INTEGER) RETURNS INTEGER
  DECLARE Current : INTEGER
  Current ← Start
  WHILE Current <> 0 DO
    IF Data[Current] = Target THEN
      RETURN Current
    ENDIF
    Current ← Pointer[Current]   // move to next node
  ENDWHILE
  RETURN 0
ENDFUNCTION

Searching a linked list is $O(n)$ — you cannot jump to the middle as you can with an array, so a binary search is not possible on a linked list.

Stack (LIFO — last in, first out). Add (PUSH) and remove (POP) at the same end, the top:

PROCEDURE Push(Item : INTEGER)
  IF Top = MaxSize THEN
    OUTPUT "Stack full"
  ELSE
    Top ← Top + 1
    StackData[Top] ← Item
  ENDIF
ENDPROCEDURE

FUNCTION Pop() RETURNS INTEGER
  IF Top = 0 THEN
    OUTPUT "Stack empty"
    RETURN -1
  ELSE
    Top ← Top - 1
    RETURN StackData[Top + 1]   // delete from the top
  ENDIF
ENDFUNCTION

Queue (FIFO — first in, first out). Insert at the rear, remove from the front:

PROCEDURE Enqueue(Item : INTEGER)   // insert at rear
  Rear ← Rear + 1
  QueueData[Rear] ← Item
ENDPROCEDURE

FUNCTION Dequeue() RETURNS INTEGER  // delete from front
  DECLARE Item : INTEGER
  Item ← QueueData[Front]
  Front ← Front + 1
  RETURN Item
ENDFUNCTION

PUSH/POP and enqueue/dequeue are all $O(1)$ — they act on a single end and do not depend on the number of items.

Linked list: nodes joined by pointers; follow Start until null (0); find = $O(n)$ .
Stack = LIFO: PUSH/POP at the same end (Top).
Queue = FIFO: enqueue at Rear, dequeue at Front.
Insert/delete on a stack or queue is $O(1)$ .

See the full worked example for algorithms →

The binary tree ADT

Nodes with left/right child pointers; smaller left, larger right → fast search.

A binary tree is an ADT made of nodes, each holding a data value and up to two child pointers — a left pointer and a right pointer. The top node is the root.

In an ordered (binary search) tree, for every node: values smaller than it go in the left subtree, and values larger go in the right subtree. This ordering lets you search by repeatedly going left or right, discarding a whole subtree at each step.

To find an item, start at the root and move left or right depending on the comparison, following child pointers (stored as a left and right array index, with 0 for 'no child'):

FUNCTION FindInTree(Target : INTEGER) RETURNS INTEGER
  DECLARE Current : INTEGER
  Current ← Root
  WHILE Current <> 0 DO
    IF Tree[Current].Value = Target THEN
      RETURN Current
    ELSE
      IF Target < Tree[Current].Value THEN
        Current ← Tree[Current].Left
      ELSE
        Current ← Tree[Current].Right
      ENDIF
    ENDIF
  ENDWHILE
  RETURN 0
ENDFUNCTION

Inserting a new value follows the same path until a null (0) child pointer is reached, then attaches the new node there. A search/insert in a balanced ordered tree is about $O(\log n)$ , because each step discards a subtree.

Binary tree: nodes with left and right child pointers; top = root.
Ordered tree: smaller values left, larger values right.
Find/insert by going left or right from the root until match or null.
Balanced ordered tree → ~ $O(\log n)$ search.

Dictionary and graph ADTs

A dictionary maps keys to values; a graph models many-to-many connections.

Dictionary — an ADT that stores key–value pairs. Each unique key maps to a value, so a value can be looked up directly by its key rather than by searching through every item.

Example: a dictionary of phone extensions might map "Ravi" → 4102, "Mei" → 4118. Asking for the key "Mei" returns 4118 directly.

Graph — an ADT that consists of nodes (vertices) joined by edges (arcs). A graph models many-to-many relationships with no fixed hierarchy: any node may connect to any number of others. Edges may be:

directed (one-way, e.g. 'follows' on social media) or undirected (two-way, e.g. 'is friends with');
weighted (the edge carries a value, e.g. a distance or cost) or unweighted.

Justifying a graph: use a graph when the data is a network of arbitrary connections — for example road networks (junctions joined by roads with distances), social networks (people joined by friendships), or web pages joined by links. A list or tree cannot represent these many-to-many links naturally.

9618 scope: you must be able to describe the features of a graph and justify its use, but you are not required to write algorithms that build or traverse a graph.

Dictionary: key → value pairs; look up a value directly by its key.
Graph: nodes (vertices) joined by edges (arcs).
Edges can be directed/undirected and weighted/unweighted.
Graph models many-to-many connections — describe & justify only (no code).

Implementing one ADT from another

Stacks, queues, lists, dictionaries and trees can be built from arrays + pointers.

A key idea in 9618 is that an ADT does not need its own special hardware — it can be implemented from built-in types (like arrays) or from another ADT. The ADT is the interface (the operations); the underlying storage is the implementation.

ADT	Can be implemented using…
Stack	an array + a single `Top` pointer (index)
Queue	an array + `Front` and `Rear` pointers
Linked list	parallel arrays (`Data`, `Pointer`) + a `Start` pointer
Dictionary	an array of records / a hash table, or two parallel arrays (keys, values)
Binary tree	nodes (records with left/right indices), or arrays for value/left/right

For example, the stack code in §3 stores its items in an ordinary ARRAY[1:MaxSize] and uses the integer Top to remember where the top of the stack is. The array is a built-in type; the stack behaviour (LIFO, PUSH/POP) is supplied by the operations we write around it.

Building from another ADT is also possible — e.g. a queue can be built on top of a linked list, or a dictionary on top of a binary tree. The point is that the same ADT can have different implementations, chosen for efficiency.

ADT = the operations (interface); the storage is the implementation.
Stack/queue/dictionary can be built from arrays + pointers/indices.
Linked list = arrays (Data, Pointer) + a Start pointer.
Binary tree = records (value, left, right) or parallel arrays.
The same ADT can have different implementations.

See the full worked example for algorithms →

Comparing algorithms with Big O

Big O measures how time and space grow with input size $n$ .

To compare algorithms fairly, we describe how their cost grows as the input size $n$ grows, using Big O notation. Big O ignores constant factors and focuses on the dominant term, so it captures behaviour for large $n$ .

Big O	Name	Example
$O(1)$	constant	accessing one array element by its index
$O(\log n)$	logarithmic	binary search (sorted data)
$O(n)$	linear	linear search; finding an item in a linked list
$O(n \log n)$	linearithmic	efficient general-purpose sorts
$O(n^2)$	quadratic	bubble sort, insertion sort (worst case)

Time complexity measures how the number of operations grows; space complexity measures how the memory used grows. Big O is used for both.

Direct array indexing is $O(1)$ — the address is calculated from the index, no searching needed.
A binary search is $O(\log n)$ because it halves the range each step — but it needs the data sorted.
Nested loops (bubble/insertion sort) give $O(n^2)$ , which grows steeply: 10× the data is ~100× the work.

Choosing an algorithm means weighing these criteria: speed (time complexity), memory (space complexity), and any preconditions (e.g. binary search needs sorted data). A faster algorithm may use more memory, or require an up-front sort, so the 'best' choice depends on the situation.

Big O: how time/space grows with input size $n$ (ignores constants).
$O(1)$ index access; $O(\log n)$ binary search; $O(n)$ linear search; $O(n^2)$ bubble/insertion.
Time complexity = operations grow; space complexity = memory grows.
Compare algorithms on speed, memory AND preconditions.

See the full worked example for algorithms →

Quick recap

Linear search ( $O(n)$ , unsorted) checks each item; binary search ( $O(\log n)$ , sorted) halves the range.
Bubble and insertion sort are $O(n^2)$ worst case but ~ $O(n)$ on nearly-sorted data; performance depends on initial order and size.
Linked list: follow pointers from Start to null; find = $O(n)$ . Stack = LIFO (Top); queue = FIFO (Front/Rear); insert/delete = $O(1)$ .
Binary tree: smaller left, larger right; find/insert by going left or right from the root.
Dictionary maps keys → values; a graph models many-to-many connections (describe & justify, no code).
ADTs can be implemented from built-in types or other ADTs (stack/queue/dictionary from arrays; list from arrays + pointers; tree from nodes).
Big O measures how time AND space grow with $n$ : $O(1)$ , $O(\log n)$ , $O(n)$ , $O(n \log n)$ , $O(n^2)$ .

Memorise this

Verbatim phrases and definitions Cambridge mark schemes credit.

Linear search = $O(n)$ , works on unsorted data.
Binary search = $O(\log n)$ , requires SORTED data, checks the middle and halves the range.
Bubble & insertion sort: worst case $O(n^2)$ , best case ~ $O(n)$ (nearly sorted).
Stack = LIFO (Top); queue = FIFO (Rear in, Front out); insert/delete = $O(1)$ .
Linked list traversal: Current ← Start, then Current ← Pointer[Current], stop at 0.
Ordered binary tree: smaller values go left, larger go right.
A graph is an ADT (nodes/vertices + edges/arcs) — describe & justify, no code required.
Big O orders: $O(1)$ , $O(\log n)$ , $O(n)$ , $O(n \log n)$ , $O(n^2)$ — for time AND space.

How it’s examined

Section 19.1 is assessed in Paper 3 (Advanced Theory, 1 h 30 min, 75 marks) — written, externally assessed — and in Paper 4 (Practical, 2 h 30 min, 75 marks). No calculator is allowed. In Paper 3 expect: writing or completing search/sort algorithms in pseudocode, completing a trace table, stating conditions (binary search needs sorted data), describing how performance varies with the number of items and the initial order, find/insert/delete algorithms for ADTs, justifying a graph, and comparing algorithms using Big O for time and space. In Paper 4 you may need to implement these algorithms and ADT operations in your chosen programming language. Always show working and traces — method marks are available even when a final value is wrong.

Sources: Cambridge International AS & A Level Computer Science 9618 syllabus (2027-2029), section 19.1. Last reviewed 2026-06-21.

Take this whole topic with you

Step-by-step worked examples — Algorithms

Step-by-step solutions to past-paper-style questions on algorithms, written exactly the way a tutor would explain them at the board.

Question type:

1Write and trace a linear search
Getting startedGraph or diagram• 9618 Paper 3 style• linear search, trace table, AO2
Question
An array Names holds the values ["Sam", "Ravi", "Mei", "Ada"] in ARRAY[1:4]. Write a FUNCTION LinearSearch that returns the index of a target name or 0 if not found, then trace a search for "Mei". (5 marks)
Step-by-step solution
1. Step 1
  A linear search checks each element in turn from the first to the last. Declare the function header and a loop counter.
  $FUNCTION LinearSearch(Target : STRING) RETURNS INTEGER\n DECLARE i : INTEGER$
2. Step 2
  Walk through the array with a FOR loop. As soon as the current element matches the target, return its index — there is no need to keep looking.
  $FOR i \leftarrow 1 TO 4\n IF Names[i] = Target THEN\n RETURN i\n ENDIF\n NEXT i$
3. Step 3
  If the loop finishes without a match, the item is absent. Return 0 to signal 'not found'.
  $RETURN 0\nENDFUNCTION$
4. Step 4
  Trace LinearSearch("Mei"). Compare each element against "Mei" until a match is found.
Answer
FUNCTION LinearSearch(Target : STRING) RETURNS INTEGER DECLARE i : INTEGER FOR i ← 1 TO 4 IF Names[i] = Target THEN RETURN i ENDIF NEXT i RETURN 0 ENDFUNCTION

Trace for LinearSearch("Mei"):

i Names[i] Names[i] = "Mei"?
1 Sam No
2 Ravi No
3 Mei Yes → RETURN 3

The function returns 3. A linear search works on unsorted data and runs in $O(n)$ time.
Examiner tip
Returning the index immediately on a match (not continuing the loop) is the efficient version examiners reward. A linear search needs no ordering of the data — that is its key advantage over binary search.
2Binary search with a full trace
Getting startedGraph or diagram• 9618 Paper 3 style• binary search, trace table, sorted data, AO2
Question
A sorted array Vals = [3, 7, 11, 18, 22, 30, 41] is stored in ARRAY[1:7]. Write a FUNCTION BinarySearch that returns the index of a target value (or 0 if absent), trace a search for 30, and state the condition the data must meet. (6 marks)
Step-by-step solution
1. Step 1
  Binary search keeps a Low and High pointer marking the part of the array still being searched. Initialise them to the first and last index.
  $FUNCTION BinarySearch(Target : INTEGER) RETURNS INTEGER\n DECLARE Low, High, Mid : INTEGER\n Low \leftarrow 1\n High \leftarrow 7$
2. Step 2
  While the search range is valid, calculate the middle index Mid (integer division discards the remainder).
  $WHILE Low <= High DO\n Mid \leftarrow (Low + High) DIV 2$
3. Step 3
  Compare the middle item with the target. If equal, return Mid. If the target is larger, discard the lower half (move Low up); otherwise discard the upper half (move High down).
  $IF Vals[Mid] = Target THEN\n RETURN Mid\n ELSE\n IF Vals[Mid] < Target THEN\n Low \leftarrow Mid + 1\n ELSE\n High \leftarrow Mid - 1\n ENDIF\n ENDIF\n ENDWHILE\n RETURN 0$
4. Step 4
  Trace BinarySearch(30). Each pass throws away half of the remaining elements.
Answer
FUNCTION BinarySearch(Target : INTEGER) RETURNS INTEGER DECLARE Low, High, Mid : INTEGER Low ← 1 High ← 7 WHILE Low <= High DO Mid ← (Low + High) DIV 2 IF Vals[Mid] = Target THEN RETURN Mid ELSE IF Vals[Mid] < Target THEN Low ← Mid + 1 ELSE High ← Mid - 1 ENDIF ENDIF ENDWHILE RETURN 0 ENDFUNCTION

Trace for BinarySearch(30) on [3, 7, 11, 18, 22, 30, 41]:

Low High Mid Vals[Mid] Action
1 7 4 18 18 < 30 → Low ← 5
5 7 6 30 match → RETURN 6

The function returns 6. Condition: the data must already be sorted. Performance is $O(\log n)$ because each comparison halves the search range.
Examiner tip
State the sorted-data condition explicitly — a binary search on unsorted data gives wrong results. Mid ← (Low + High) DIV 2 uses integer division; the loop ends when Low > High (item absent).
3Insertion sort with a trace
Building confidenceMulti-step problem• 9618 Paper 3 style• insertion sort, trace table, AO2
Question
Write a PROCEDURE InsertionSort for an integer array A in ARRAY[1:n], then trace it on the list [5, 2, 4, 1]. (6 marks)
Step-by-step solution
1. Step 1
  Insertion sort grows a sorted section at the left of the array. From the second element onward, take the current value as Key and remember its position.
  $PROCEDURE InsertionSort()\n DECLARE i, j, Key : INTEGER\n FOR i \leftarrow 2 TO n\n Key \leftarrow A[i]\n j \leftarrow i - 1$
2. Step 2
  Shift every element in the sorted section that is larger than Key one place to the right, opening a gap for Key.
  $WHILE j >= 1 AND A[j] > Key DO\n A[j + 1] \leftarrow A[j]\n j \leftarrow j - 1\n ENDWHILE$
3. Step 3
  Drop Key into the gap, then move on to the next element. After each outer pass the left section is sorted.
  $A[j + 1] \leftarrow Key\n NEXT i\nENDPROCEDURE$
4. Step 4
  Trace on [5, 2, 4, 1]. Each pass inserts A[i] into its correct place among the items to its left.
Answer
PROCEDURE InsertionSort() DECLARE i, j, Key : INTEGER FOR i ← 2 TO n Key ← A[i] j ← i - 1 WHILE j >= 1 AND A[j] > Key DO A[j + 1] ← A[j] j ← j - 1 ENDWHILE A[j + 1] ← Key NEXT i ENDPROCEDURE

Trace on [5, 2, 4, 1]:

Pass (i) Key Array after inserting Key
start – 5 2 4 1
2 2 2 5 4 1
3 4 2 4 5 1
4 1 1 2 4 5

Final sorted array: 1 2 4 5. Insertion sort is $O(n^2)$ in the worst case but ~ $O(n)$ on a nearly-sorted list.
Examiner tip
The inner WHILE must test j >= 1 BEFORE A[j] > Key so it stops at the start of the array. Insertion sort is adaptive: on data that is already (nearly) sorted, the inner loop barely runs, giving best-case $O(n)$ .
4Stack ADT: insert (PUSH) and delete (POP)
Building confidenceMulti-step problem• 9618 Paper 3 style• stack, queue, ADT, insert, delete, AO2
Question
A stack is implemented with StackData : ARRAY[1:MaxSize] OF INTEGER, a Top pointer (0 when empty) and MaxSize. (a) Write PROCEDURE Push(Item) that inserts an item, guarding against a full stack. (b) Write FUNCTION Pop() that deletes and returns the top item, guarding against an empty stack. (c) Briefly state how inserting into a (linear) queue using a Rear pointer differs. (6 marks)
Step-by-step solution
1. Step 1
  A stack is LIFO (last in, first out): items are inserted and deleted at the same end, the top. For PUSH (insert), first check the stack is not full.
  $PROCEDURE Push(Item : INTEGER)\n IF Top = MaxSize THEN\n OUTPUT "Stack full"$
2. Step 2
  If there is room, move the Top pointer up by one, then store the new item at that position.
  $ELSE\n Top \leftarrow Top + 1\n StackData[Top] \leftarrow Item\n ENDIF\nENDPROCEDURE$
3. Step 3
  For POP (delete), first check the stack is not empty (Top = 0). If there is an item, read the value at Top, then move the Top pointer down by one so that slot is logically removed. Return the value read.
  $FUNCTION Pop() RETURNS INTEGER\n DECLARE Item : INTEGER\n IF Top = 0 THEN\n OUTPUT "Stack empty"\n RETURN -1\n ELSE\n Item \leftarrow StackData[Top]\n Top \leftarrow Top - 1\n RETURN Item\n ENDIF\nENDFUNCTION$
4. Step 4
  A queue is FIFO (first in, first out): items are inserted at the rear and deleted from the front. Inserting (enqueue) increases the Rear pointer and stores the item there — a different end from where items are deleted.
Answer
(a) Push (insert) onto a stack:

PROCEDURE Push(Item : INTEGER) IF Top = MaxSize THEN OUTPUT "Stack full" ELSE Top ← Top + 1 StackData[Top] ← Item ENDIF ENDPROCEDURE

(b) Pop (delete) from a stack:

FUNCTION Pop() RETURNS INTEGER DECLARE Item : INTEGER IF Top = 0 THEN OUTPUT "Stack empty" RETURN -1 ELSE Item ← StackData[Top] Top ← Top - 1 RETURN Item ENDIF ENDFUNCTION

(c) A queue (FIFO) inserts at the rear: Rear ← Rear + 1 then QueueData[Rear] ← Item (after a full check). Items are deleted from the front, so a queue uses two pointers at opposite ends, whereas a stack uses one pointer (Top) for both insert and delete. PUSH, POP and enqueue are all $O(1)$ operations.
Examiner tip
Test the full condition BEFORE incrementing on PUSH, and the empty condition (Top = 0) BEFORE reading on POP. Deleting from a stack does not erase the data — it just moves Top down so the slot is reused. Remember the directions: stack = one end (LIFO); queue = rear in, front out (FIFO).
5Find an item in a linked list
StretchMulti-step problem• 9618 Paper 3 style• linked list, pointers, ADT, AO2
Question
A linked list is stored as two parallel arrays, Data : ARRAY[1:n] and Pointer : ARRAY[1:n], with a Start pointer holding the index of the first node. A pointer of 0 marks the end of the list. Write a FUNCTION FindNode that returns the index of the node containing a target value, or 0 if it is not present. (6 marks)
Step-by-step solution
1. Step 1
  Begin at the node referenced by Start. Use a 'current' index to walk the list one node at a time.
  $FUNCTION FindNode(Target : INTEGER) RETURNS INTEGER\n DECLARE Current : INTEGER\n Current \leftarrow Start$
2. Step 2
  While we have not run off the end of the list (Current <> 0), check the data at the current node. If it matches, return that index.
  $WHILE Current <> 0 DO\n IF Data[Current] = Target THEN\n RETURN Current\n ENDIF$
3. Step 3
  Otherwise follow the pointer to the next node. When Current becomes 0 the list is exhausted, so return 0.
  $Current \leftarrow Pointer[Current]\n ENDWHILE\n RETURN 0\nENDFUNCTION$
Answer
FUNCTION FindNode(Target : INTEGER) RETURNS INTEGER DECLARE Current : INTEGER Current ← Start WHILE Current <> 0 DO IF Data[Current] = Target THEN RETURN Current ENDIF Current ← Pointer[Current] ENDWHILE RETURN 0 ENDFUNCTION

The traversal follows the chain of pointers from Start until either the target is found or a null pointer (0) is reached. Searching a linked list is $O(n)$ — you cannot jump to the middle as you can with an array, because nodes are reached only by following pointers.
Examiner tip
The list is traversed by repeatedly assigning Current ← Pointer[Current]; the loop must stop on the null pointer (0). A common slip is to dereference Data[Current] after Current becomes 0 — guard with WHILE Current <> 0 so this never happens.
6Compare algorithms using Big O
StretchIdentify & classify• 9618 Paper 3 style• Big O, time complexity, comparison, AO1, AO2
Question
(a) State the Big O time complexity of a linear search, a binary search, a bubble sort and an insertion sort. (b) Explain why binary search is faster than linear search for large data sets, and state the trade-off involved. (6 marks)
Step-by-step solution
1. Step 1
  Recall what each algorithm does at scale. Linear search checks each item once → grows linearly with n. Binary search halves the range each step → grows logarithmically.
  $\text{Linear search} = O(n), \quad \text{Binary search} = O(\log n)$
2. Step 2
  Bubble sort and insertion sort both compare/shift items in nested loops → roughly n × n operations in the worst case.
  $\text{Bubble sort} = O(n^2), \quad \text{Insertion sort} = O(n^2)$
3. Step 3
  Compare the growth. For n = 1000, linear search may need up to 1000 comparisons but binary search needs only about 10 ( $\log_2 1000 \approx 10$ ). As n grows, $\log n$ grows far more slowly than $n$ .
4. Step 4
  State the trade-off: binary search only works on sorted data, so you must pay the cost of sorting first (e.g. $O(n^2)$ for bubble/insertion, or $O(n \log n)$ for a good sort). For a one-off search on unsorted data, a linear search can be the better choice.
Answer
(a) Linear search $O(n)$ ; binary search $O(\log n)$ ; bubble sort $O(n^2)$ ; insertion sort $O(n^2)$ .

(b) Binary search is faster for large data because it discards half of the remaining items at each comparison, so the number of comparisons grows as $O(\log n)$ rather than $O(n)$ — e.g. ~10 comparisons for 1000 items versus up to 1000 for a linear search. Trade-off: binary search requires the data to be sorted first, which has its own cost (up to $O(n^2)$ for a simple sort). For a single search of unsorted data, linear search avoids that overhead.
Examiner tip
Big O describes how work grows with input size $n$ , ignoring constant factors. The discriminating point is the trade-off: binary search's speed is only available once the data is sorted, so quote both the complexity AND the sorting precondition.

i	Names[i]	Names[i] = "Mei"?
1	Sam	No
2	Ravi	No
3	Mei	Yes → RETURN 3

Low	High	Mid	Vals[Mid]	Action
1	7	4	18	18 < 30 → Low ← 5
5	7	6	30	match → RETURN 6

Pass (i)	Key	Array after inserting Key
start	–	5 2 4 1
2	2	2 5 4 1
3	4	2 4 5 1
4	1	1 2 4 5

Model Answers — Algorithms

High-scoring sample answers for algorithms on the Cambridge IGCSE paper, with examiner-style notes mapping each response to the mark scheme and assessment objectives.

Question 1
9618 Paper 3 style2 marks
State two differences between a linear search and a binary search. (2 marks)
Model answer
A linear search checks each item in turn from the start, whereas a binary search repeatedly checks the middle item and discards half the remaining items.

A linear search works on unsorted data, whereas a binary search requires the data to be sorted first.
Why this scores
1 mark per valid difference (max 2). Either the 'check each vs halve the range' contrast or the 'unsorted vs sorted' contrast earns a mark. Vague answers like 'binary is faster' without saying why score nothing.
Question 2
9618 Paper 3 style3 marks
A programmer wants to use a binary search on a list of customer IDs. State the condition the list must meet, and explain what happens at each step of the search. (3 marks)
Model answer
Condition: the list of IDs must be sorted (e.g. into ascending order) before the search begins.

At each step: the algorithm looks at the middle item of the current search range. If it equals the target, the search ends. If the target is larger, the lower half is discarded; if the target is smaller, the upper half is discarded. This repeats on the remaining half until the item is found or the range is empty.
Why this scores
1 mark for the sorted-data condition; up to 2 marks for describing the middle-check and the halving of the range. The word 'middle' and the idea of 'discarding half' are the key credit points.
Question 3
9618 Paper 3 style4 marks
Compare the performance of a linear search and a binary search as the number of items in the data set increases. Refer to Big O notation in your answer. (4 marks)
Model answer
A linear search has time complexity $O(n)$ : in the worst case it must check every one of the $n$ items, so the number of comparisons grows in direct proportion to the size of the data.

A binary search has time complexity $O(\log n)$ : each comparison discards half of the remaining items, so the number of comparisons grows only logarithmically. For example, doubling the data adds just one extra comparison to a binary search but can double the work of a linear search.

Therefore, as the number of items grows large, binary search becomes dramatically faster — but only if the data is already sorted, which is the condition a linear search does not need.
Why this scores
Marks for: linear = $O(n)$ (1); binary = $O(\log n)$ (1); explaining the growth difference / halving (1); noting the sorted-data requirement (1). Tie the Big O notation to a concrete behaviour ('checks every item' / 'halves the range') for full credit.
Question 4
9618 Paper 3 style5 marks
Explain how the performance of an insertion sort depends on the initial order of the data, and state its best-case and worst-case Big O time complexity. (5 marks)
Model answer
Insertion sort builds a sorted section by taking each next item and inserting it into its correct place among the items already sorted, shifting larger items to the right.

If the data is already (nearly) sorted, each new item is usually already in place, so the inner shifting loop hardly runs. The algorithm makes roughly one comparison per item, giving a best case of $O(n)$ .

If the data is in reverse order, every new item must be shifted past all the items before it, so the inner loop runs the maximum number of times, giving a worst case of $O(n^2)$ .

Performance therefore depends on both the initial order of the data and the number of items: more items, and data that is far from sorted, both increase the work. This adaptiveness makes insertion sort efficient for small or nearly-sorted lists.
Why this scores
Marks for: describing the insert-and-shift method (1); best case $O(n)$ on (nearly) sorted data (1); worst case $O(n^2)$ on reverse-ordered data (1); linking performance to initial order (1) and to number of items (1). Saying insertion sort is 'always $O(n^2)$ ' loses the adaptiveness credit.
Question 5
9618 Paper 3 style6 marks
State the Big O time complexity of each of the following, and for each give a one-line justification: (a) a linear search, (b) a binary search, (c) a bubble sort, (d) accessing one element of an array by its index. (6 marks)
Model answer
(a) Linear search — $O(n)$ . In the worst case it must compare the target with every one of the $n$ items.

(b) Binary search — $O(\log n)$ . Each comparison discards half of the remaining items, so the work grows logarithmically (the data must be sorted).

(c) Bubble sort — $O(n^2)$ . It uses nested loops, comparing and swapping adjacent items, so the number of comparisons grows with $n \times n$ .

(d) Array access by index — $O(1)$ . The address is calculated directly from the index, so the time is constant regardless of the array size.
Why this scores
1 mark for each correct complexity (4) plus up to 2 marks for sound justifications. $O(1)$ for direct array indexing is a frequently-missed point — emphasise that an index is a direct calculation, unlike following pointers in a linked list ( $O(n)$ ).
Question 6
9618 Paper 3 style6 marks
A social-media company stores 'friend' connections between users. (a) Explain why a graph is a suitable abstract data type (ADT) for this data. (b) State two features of a graph. (c) State one reason why an ADT such as a stack might be implemented using an array. (6 marks)
Model answer
(a) A graph is suitable because friendships are many-to-many relationships: any user can be connected to many other users, and those connections have no hierarchy or fixed order. A graph models exactly this — items (users) joined by connections in any pattern — which a list or tree cannot represent naturally.

(b) Two features of a graph: it consists of nodes (vertices) joined by edges (arcs); the edges may be directed or undirected and may carry weights (and a node may connect to any number of other nodes).

(c) A stack can be implemented using an array because the array provides ready-made indexed storage, so the stack only needs a single Top pointer to track the position — this reuses a built-in type rather than building the storage from scratch (and gives $O(1)$ push/pop).
Why this scores
(a) up to 2 marks for justifying the graph (many-to-many / no hierarchy / models arbitrary connections). (b) 1 mark per feature, max 2 (nodes/vertices, edges/arcs, directed/undirected, weighted). (c) up to 2 marks: an ADT can be built from a simpler built-in type (array) plus pointers/indices. Note 9618 requires you to describe and justify a graph but not to write code for one.

Key Definitions and Keywords — Algorithms

Definitions to memorise and the exact keywords mark schemes credit for algorithms answers — sharpened from recent examiner reports for the 2026 Cambridge IGCSE sitting.

Linear search
Examiner keyword
A search that checks each element of a list in turn, from the first to the last, until the target is found or the end is reached. It works on unsorted data and has time complexity O(n).
Binary search
Examiner keyword
A search that repeatedly examines the middle item of a SORTED list and discards the half that cannot contain the target, halving the search range each time. Time complexity O(log n).
Insertion sort
Examiner keyword
A sorting algorithm that builds a sorted section by taking each next item and inserting it into its correct position among the items already sorted, shifting larger items along. Worst case O(n^2), best case ~O(n).
Bubble sort
Examiner keyword
A sorting algorithm that repeatedly passes through the list, comparing adjacent items and swapping them if they are out of order, so large values 'bubble' to the end. Worst case O(n^2).
Abstract data type (ADT)
Examiner keyword
A collection of data together with a defined set of operations on it, described by what it does rather than how it is stored. Examples include stacks, queues, linked lists, binary trees, dictionaries and graphs.
Linked list
Examiner keyword
An ADT in which each item (node) holds its data and a pointer to the next node. A Start pointer marks the first node and a null pointer (0) marks the end. Items are found by following the chain of pointers.
Binary tree
Examiner keyword
An ADT made of nodes, each with a data value and up to two child pointers (left and right). In an ordered binary tree, smaller values go left and larger values go right, allowing fast searching.
Stack
Examiner keyword
A LIFO (last in, first out) ADT where items are added (PUSH) and removed (POP) at the same end, the top, tracked by a Top pointer.
Queue
Examiner keyword
A FIFO (first in, first out) ADT where items are added at the rear (enqueue) and removed from the front (dequeue), tracked by Front and Rear pointers.
Dictionary
Examiner keyword
An ADT that stores key–value pairs, where each unique key maps to a value, allowing a value to be looked up directly by its key.
Graph
Examiner keyword
An ADT consisting of nodes (vertices) connected by edges (arcs), which may be directed or undirected and weighted. It models many-to-many relationships with no fixed hierarchy. In 9618 you describe and justify a graph but are not required to code it.
Big O notation
Examiner keyword
A notation that describes how the time or memory used by an algorithm grows with the size of the input n, ignoring constant factors. Common orders: O(1), O(log n), O(n), O(n log n), O(n^2).
Time complexity
Examiner keyword
A measure, expressed in Big O notation, of how the number of operations an algorithm performs grows as the size of the input increases.
Space complexity
Examiner keyword
A measure, expressed in Big O notation, of how the amount of memory an algorithm needs grows as the size of the input increases.

Common Mistakes and Misconceptions — Algorithms

The traps other students keep falling into on algorithms questions — taken from recent Cambridge IGCSE examiner reports and mark schemes — and how to avoid them.

✕Applying a binary search to unsorted data and expecting a correct result.
Examiner reports note that the sorted-data condition is the most frequently omitted point in binary-search questions.
Why it happens
Students remember binary search is 'faster' but forget that the halving logic only works when the data is in order.
How to avoid it
Always state and check the precondition: a binary search requires SORTED data. On unsorted data, use a linear search or sort the data first.
✕Writing a search loop that runs off the end of the data — e.g. dereferencing a node after the pointer has become 0, or letting Low exceed High.
Why it happens
The stopping condition is placed after the access, or the 'not found' case is forgotten.
How to avoid it
Put the boundary test in the loop condition: WHILE Current <> 0 DO for a linked list and WHILE Low <= High DO for a binary search, and always return 0 (not found) after the loop.
✕Stating that insertion sort (or bubble sort) is always O(n^2) regardless of the data.
Why it happens
Students memorise the worst case and ignore how performance depends on the initial order.
How to avoid it
Remember these sorts are adaptive: on (nearly) sorted data the inner loop barely runs, giving a best case of ~O(n). Performance depends on both initial order and number of items.
✕Confusing where a stack and a queue add and remove items (e.g. removing from the front of a stack).
Why it happens
LIFO and FIFO are easily mixed up, especially under exam pressure.
How to avoid it
Stack = LIFO: PUSH and POP at the SAME end (Top). Queue = FIFO: add at the REAR, remove from the FRONT (two pointers).
✕When traversing a linked list, forgetting to advance to the next node, causing an infinite loop.
Why it happens
Students check Data[Current] but never update Current ← Pointer[Current].
How to avoid it
Inside the traversal loop, always follow the pointer to the next node before the next iteration: Current ← Pointer[Current].
✕Mixing up the Big O orders — e.g. calling binary search O(n) or array indexing O(n).
Why it happens
The orders are learned as a list without connecting them to what the algorithm actually does.
How to avoid it
Link each order to a behaviour: direct index access = O(1); halving the range = O(log n); checking each item = O(n); nested loops = O(n^2).

Algorithms

Detailed Study Notes

At a glance

What you’ll learn

Quick recap

Memorise this

How it’s examined

Take this whole topic with you

1Write and trace a linear search

2Binary search with a full trace

3Insertion sort with a trace

4Stack ADT: insert (PUSH) and delete (POP)

5Find an item in a linked list

6Compare algorithms using Big O

Linear search

Binary search

Insertion sort

Bubble sort

Abstract data type (ADT)

Linked list

Binary tree

Stack

Queue

Dictionary

Graph

Big O notation

Time complexity

Space complexity

✕Applying a binary search to unsorted data and expecting a correct result.

✕Writing a search loop that runs off the end of the data — e.g. dereferencing a node after the pointer has become 0, or letting Low exceed High.

✕Stating that insertion sort (or bubble sort) is always O(n^2) regardless of the data.

✕Confusing where a stack and a queue add and remove items (e.g. removing from the front of a stack).

✕When traversing a linked list, forgetting to advance to the next node, causing an infinite loop.

✕Mixing up the Big O orders — e.g. calling binary search O(n) or array indexing O(n).