2.3.1 Algorithms
2.3.1(a) Big O Notation
Definition
Big O notation describes the upper bound (worst-case) growth rate of an algorithm's time or space complexity as the input size increases. It provides a standardised way to compare algorithm efficiency.
Common Big O Complexities
Key Point
| Big O | Name | Typical example | Growth intuition |
|---|---|---|---|
| O(1) | Constant | Array lookup by index | Cost stays about the same as n grows |
| O(log n) | Logarithmic | Binary search | Doubling n adds only a small extra cost |
| O(n) | Linear | Linear search | Cost grows in direct proportion to n |
| O(n log n) | Log-linear | Merge sort, quicksort (average) | Efficient for large sorting tasks |
| O(n²) | Quadratic | Bubble sort, insertion sort (worst/avg) | Cost grows rapidly as n increases |
| O(2ⁿ) | Exponential | Brute-force recursion | Explodes quickly; impractical at scale |
Time vs Space Complexity
Key Point
| Complexity type | What it measures | Typical trade-off |
|---|---|---|
| Time complexity | How runtime grows with input size n | Faster runtime may need extra memory |
| Space complexity | How extra memory use grows with n | Lower memory usage may increase runtime |
2.3.1(b) Searching Algorithms
Linear Search
Definition
Linear Search checks each element one by one until the target is found or all elements are checked. Works on both sorted and unsorted data.
text
function linearSearch(array, target):
for i = 0 to length(array) - 1:
if array[i] == target then
return i
end if
end for
return -1 // Not found
end functionWorked Example
Linear Search: Find "Apple" in [Banana, Orange, Apple, Kiwi, Mango]
| Step | Comparison | Action |
|---|---|---|
| 1 | Index 0: Banana ≠ Apple | Continue |
| 2 | Index 1: Orange ≠ Apple | Continue |
| 3 | Index 2: Apple = Apple | Return index 2 |
Key Point
Linear Search Complexity:
• Best Case: O(1) - target at first position
• Worst Case: O(n) - target at end or not present
• Average Case: O(n)
When to use:
• Small datasets
• Unsorted data
• Searching linked lists (no random access)
• Best Case: O(1) - target at first position
• Worst Case: O(n) - target at end or not present
• Average Case: O(n)
When to use:
• Small datasets
• Unsorted data
• Searching linked lists (no random access)
Binary Search
Definition
Binary Search finds an element in a sorted array by repeatedly dividing the search space in half. Much more efficient than linear search for large datasets.
text
function binarySearch(array, target):
low = 0
high = length(array) - 1
while low <= high:
mid = (low + high) DIV 2
if array[mid] == target then
return mid
elseif array[mid] < target then
low = mid + 1 // Search right half
else
high = mid - 1 // Search left half
end if
end while
return -1 // Not found
end functionWorked Example
Binary Search: Find "Dylan" in sorted array
Array: [Alice, Bob, Charlie, Dylan, Ellie, Franz, Gabbie, Hugo, Ingrid]
Array: [Alice, Bob, Charlie, Dylan, Ellie, Franz, Gabbie, Hugo, Ingrid]
| Step | low/high/mid | Mid value | Decision |
|---|---|---|---|
| 1 | low=0, high=8, mid=4 | Ellie | Dylan < Ellie → high = 3 |
| 2 | low=0, high=3, mid=1 | Bob | Dylan > Bob → low = 2 |
| 3 | low=2, high=3, mid=2 | Charlie | Dylan > Charlie → low = 3 |
| 4 | low=3, high=3, mid=3 | Dylan | Found |
Key Point
Binary Search Complexity:
• Best Case: O(1) - target is middle element
• Worst Case: O(log n) - repeatedly halving
• Average Case: O(log n)
Critical Requirement: Data MUST be sorted!
Comparison: For n=1,000,000 items:
• Linear search: up to 1,000,000 comparisons
• Binary search: maximum 20 comparisons
• Best Case: O(1) - target is middle element
• Worst Case: O(log n) - repeatedly halving
• Average Case: O(log n)
Critical Requirement: Data MUST be sorted!
Comparison: For n=1,000,000 items:
• Linear search: up to 1,000,000 comparisons
• Binary search: maximum 20 comparisons
2.3.1(c) Sorting Algorithms
Bubble Sort
Definition
Bubble Sort is a straightforward, comparison-based sorting algorithm that repeatedly steps through the list, comparing adjacent elements, and swapping them if they are in the wrong order. The largest element "bubbles" to the top with each pass.
text
procedure bubbleSort(array):
n = length(array)
for i = 0 to n - 1:
swapped = False
for j = 0 to n - i - 2:
if array[j] > array[j + 1] then
// Swap elements
temp = array[j]
array[j] = array[j + 1]
array[j + 1] = temp
swapped = True
end if
end for
// Optimisation: stop if no swaps
if not swapped then
break
end if
end for
end procedureWorked Example
Bubble Sort Trace: [4, 9, 1, 6, 7]
Pass 1:
• Compare 4, 9: No swap → [4, 9, 1, 6, 7]
• Compare 9, 1: Swap → [4, 1, 9, 6, 7]
• Compare 9, 6: Swap → [4, 1, 6, 9, 7]
• Compare 9, 7: Swap → [4, 1, 6, 7, 9]
• 9 is now in final position
Pass 2:
• Compare 4, 1: Swap → [1, 4, 6, 7, 9]
• Compare 4, 6: No swap
• Compare 6, 7: No swap
• Array is sorted!
Pass 1:
• Compare 4, 9: No swap → [4, 9, 1, 6, 7]
• Compare 9, 1: Swap → [4, 1, 9, 6, 7]
• Compare 9, 6: Swap → [4, 1, 6, 9, 7]
• Compare 9, 7: Swap → [4, 1, 6, 7, 9]
• 9 is now in final position
Pass 2:
• Compare 4, 1: Swap → [1, 4, 6, 7, 9]
• Compare 4, 6: No swap
• Compare 6, 7: No swap
• Array is sorted!
Key Point
Bubble Sort Complexity:
• Best Case: O(n) - array already sorted (with optimisation)
• Worst Case: O(n²) - array in reverse order
• Average Case: O(n²)
Why inefficient for large datasets:
• Quadratic growth makes it very slow for large n
• Many unnecessary comparisons even when nearly sorted
When useful:
• Small datasets
• Nearly sorted data (with optimisation)
• Educational purposes (simple to understand)
• Best Case: O(n) - array already sorted (with optimisation)
• Worst Case: O(n²) - array in reverse order
• Average Case: O(n²)
Why inefficient for large datasets:
• Quadratic growth makes it very slow for large n
• Many unnecessary comparisons even when nearly sorted
When useful:
• Small datasets
• Nearly sorted data (with optimisation)
• Educational purposes (simple to understand)
Insertion Sort
Definition
Insertion Sort builds the final sorted array one item at a time, like sorting playing cards in your hand. It picks elements from the unsorted part and places them in the correct position in the sorted part.
text
procedure insertionSort(array):
n = length(array)
for i = 1 to n - 1:
key = array[i]
j = i - 1
// Move elements greater than key one position ahead
while j >= 0 AND array[j] > key:
array[j + 1] = array[j]
j = j - 1
end while
array[j + 1] = key
end for
end procedureWorked Example
Insertion Sort Trace: [4, 9, 1, 6, 7]
i = 1 (insert 9):
• Sorted: [4], Unsorted: [9, 1, 6, 7]
• 9 > 4, insert after → [4, 9, 1, 6, 7]
i = 2 (insert 1):
• Sorted: [4, 9], Unsorted: [1, 6, 7]
• 1 < 9, shift 9 right
• 1 < 4, shift 4 right
• Insert 1 at start → [1, 4, 9, 6, 7]
i = 3 (insert 6):
• Sorted: [1, 4, 9], Unsorted: [6, 7]
• 6 < 9, shift 9 right
• 6 > 4, insert after 4 → [1, 4, 6, 9, 7]
i = 4 (insert 7):
• Insert after 6 → [1, 4, 6, 7, 9] ✓
i = 1 (insert 9):
• Sorted: [4], Unsorted: [9, 1, 6, 7]
• 9 > 4, insert after → [4, 9, 1, 6, 7]
i = 2 (insert 1):
• Sorted: [4, 9], Unsorted: [1, 6, 7]
• 1 < 9, shift 9 right
• 1 < 4, shift 4 right
• Insert 1 at start → [1, 4, 9, 6, 7]
i = 3 (insert 6):
• Sorted: [1, 4, 9], Unsorted: [6, 7]
• 6 < 9, shift 9 right
• 6 > 4, insert after 4 → [1, 4, 6, 9, 7]
i = 4 (insert 7):
• Insert after 6 → [1, 4, 6, 7, 9] ✓
Key Point
Insertion Sort Complexity:
• Best Case: O(n) - array already sorted
• Worst Case: O(n²) - array in reverse order
• Average Case: O(n²)
Advantage over Bubble Sort:
• Better for nearly sorted data
• Fewer swaps required
• Simple implementation
• Efficient for small datasets
• Best Case: O(n) - array already sorted
• Worst Case: O(n²) - array in reverse order
• Average Case: O(n²)
Advantage over Bubble Sort:
• Better for nearly sorted data
• Fewer swaps required
• Simple implementation
• Efficient for small datasets
Merge Sort
Definition
Merge Sort is an efficient, stable, divide-and-conquer sorting algorithm. It divides the array into two halves, recursively sorts each half, then merges the sorted halves.
text
function mergeSort(array):
if length(array) <= 1 then
return array
end if
// DIVIDE
mid = length(array) DIV 2
left = mergeSort(array[0..mid-1])
right = mergeSort(array[mid..end])
// CONQUER (merge)
return merge(left, right)
end function
function merge(left, right):
result = []
while left is not empty AND right is not empty:
if left[0] <= right[0] then
append left[0] to result
remove left[0] from left
else
append right[0] to result
remove right[0] from right
end if
end while
// Add remaining elements
append remaining left to result
append remaining right to result
return result
end functionWorked Example
Merge Sort Trace: [7, 4, 2, 6]
| Phase | Working |
|---|---|
| Divide | [7,4,2,6] → [7,4] + [2,6] → [7]+[4] and [2]+[6] |
| Merge sublists | [7]+[4] → [4,7]; [2]+[6] → [2,6] |
| Final merge | [4,7] + [2,6] → [2,4,6,7] |
Key Point
Merge Sort Complexity:
• Best Case: O(n log n)
• Worst Case: O(n log n)
• Average Case: O(n log n)
• Space: O(n) - requires additional memory
Why preferred for large datasets:
• Guaranteed O(n log n) performance
• Stable sort (maintains relative order)
• Predictable regardless of input
Trade-off: Requires extra memory for merging
• Best Case: O(n log n)
• Worst Case: O(n log n)
• Average Case: O(n log n)
• Space: O(n) - requires additional memory
Why preferred for large datasets:
• Guaranteed O(n log n) performance
• Stable sort (maintains relative order)
• Predictable regardless of input
Trade-off: Requires extra memory for merging
Quick Sort
Definition
Quick Sort is a divide-and-conquer sorting algorithm that selects a pivot element and partitions the array such that elements less than the pivot come before it, and elements greater come after. This process repeats recursively.
text
function quickSort(array, low, high):
if low < high then
// Partition and get pivot position
pivotIndex = partition(array, low, high)
// Recursively sort sub-arrays
quickSort(array, low, pivotIndex - 1)
quickSort(array, pivotIndex + 1, high)
end if
end function
function partition(array, low, high):
pivot = array[high] // Choose last element as pivot
i = low - 1
for j = low to high - 1:
if array[j] <= pivot then
i = i + 1
swap array[i] and array[j]
end if
end for
swap array[i + 1] and array[high]
return i + 1
end functionWorked Example
Quick Sort Trace: [9, 4, 7, 8, 6, 3, 1, 5, 2]
First partition (pivot = 2):
• Elements < 2: [1]
• Elements > 2: [9, 4, 7, 8, 6, 3, 5]
• Result: [1, 2, 9, 4, 7, 8, 6, 3, 5]
Recursively sort left [1]: Already sorted
Recursively sort right [9, 4, 7, 8, 6, 3, 5]:
• Pivot = 5
• Left: [4, 3], Right: [9, 7, 8, 6]
• Result: [4, 3, 5, 9, 7, 8, 6]
Continue recursively...
Final sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9]
First partition (pivot = 2):
• Elements < 2: [1]
• Elements > 2: [9, 4, 7, 8, 6, 3, 5]
• Result: [1, 2, 9, 4, 7, 8, 6, 3, 5]
Recursively sort left [1]: Already sorted
Recursively sort right [9, 4, 7, 8, 6, 3, 5]:
• Pivot = 5
• Left: [4, 3], Right: [9, 7, 8, 6]
• Result: [4, 3, 5, 9, 7, 8, 6]
Continue recursively...
Final sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Key Point
Quick Sort Complexity:
• Best Case: O(n log n) - balanced partitions
• Worst Case: O(n²) - unbalanced partitions (bad pivot choice)
• Average Case: O(n log n)
• Space: O(log n) - in-place sorting
Pivot choice matters:
• First/last element: Risk of O(n²) for sorted data
• Random element: Usually good
• Median-of-three: Better balance
• Best Case: O(n log n) - balanced partitions
• Worst Case: O(n²) - unbalanced partitions (bad pivot choice)
• Average Case: O(n log n)
• Space: O(log n) - in-place sorting
Pivot choice matters:
• First/last element: Risk of O(n²) for sorted data
• Random element: Usually good
• Median-of-three: Better balance
2.3.1(d) Dijkstra's Shortest Path Algorithm
Definition
Dijkstra's Algorithm finds the shortest path between nodes in a weighted graph. It maintains a set of nodes whose shortest distance from the source is known.
How Dijkstra's Algorithm Works
text
procedure dijkstra(graph, source):
// Initialise distances
for each vertex v in graph:
distance[v] = INFINITY
visited[v] = False
end for
distance[source] = 0
while there are unvisited vertices:
// Pick unvisited vertex with smallest distance
current = vertex with minimum distance where visited[current] == False
visited[current] = True
// Update distances to neighbours
for each neighbour of current:
if not visited[neighbour] then
newDist = distance[current] + weight(current, neighbour)
if newDist < distance[neighbour] then
distance[neighbour] = newDist
end if
end if
end for
end while
return distance
end procedureKey Point
| Dijkstra aspect | Notes |
|---|---|
| Type | Greedy algorithm |
| Purpose | Shortest path from source in weighted graph |
| Requirement | Non-negative edge weights |
| Output | Shortest known distance to each reachable vertex |
| Core step | Action |
| --- | --- |
| 1 | Initialise source distance = 0, others = ∞ |
| 2 | Pick unvisited node with smallest tentative distance |
| 3 | Relax/update neighbour distances |
| 4 | Mark node visited |
| 5 | Repeat until all reachable nodes processed |
2.3.1(e) A* Algorithm
Definition
A* (A-Star) is a pathfinding algorithm that improves on Dijkstra's by using heuristics to prioritise paths that appear closer to the goal. Widely used in games and AI.
How A* Works
text
function aStar(graph, start, goal):
openSet = [start] // Nodes to evaluate
closedSet = [] // Already evaluated
gScore[start] = 0 // Cost from start
fScore[start] = heuristic(start, goal) // Estimated total cost
while openSet is not empty:
current = node in openSet with lowest fScore
if current == goal then
return reconstructPath(current)
end if
move current from openSet to closedSet
for each neighbour of current:
if neighbour in closedSet then
continue
end if
tentativeG = gScore[current] + dist(current, neighbour)
if neighbour not in openSet then
add neighbour to openSet
elseif tentativeG >= gScore[neighbour] then
continue // Not a better path
end if
// Best path found
cameFrom[neighbour] = current
gScore[neighbour] = tentativeG
fScore[neighbour] = gScore[neighbour] + heuristic(neighbour, goal)
end for
end while
return FAILURE // No path found
end functionA* Formula
Key Point
f(n) = g(n) + h(n)
| Term | Meaning |
|---|---|
| g(n) | Actual cost from start node to n |
| h(n) | Heuristic estimate from n to goal |
| f(n) | Estimated total path cost through n |
| Heuristic/comparison point | Notes |
| --- | --- |
| Manhattan distance | Useful for grid movement |
| Euclidean distance | Straight-line estimate |
| A* vs Dijkstra | A* usually explores fewer nodes; with admissible heuristic it still finds optimal path |
Exam Tip
Exam Tips for 2.3.1 Algorithms:
• Know Big O notation for time and space complexity
• Be able to trace linear and binary search step by step
• Understand binary search requires sorted data
• Know how all four sorting algorithms work (bubble, insertion, merge, quick)
• Be able to trace sorting algorithms with examples
• Know Big O complexities: bubble/insertion O(n²), merge/quick O(n log n)
• Understand Dijkstra's algorithm for shortest path
• Know A* formula: f(n) = g(n) + h(n)
• Compare algorithms using Big O notation
• Know when to use each algorithm based on data characteristics
• Know Big O notation for time and space complexity
• Be able to trace linear and binary search step by step
• Understand binary search requires sorted data
• Know how all four sorting algorithms work (bubble, insertion, merge, quick)
• Be able to trace sorting algorithms with examples
• Know Big O complexities: bubble/insertion O(n²), merge/quick O(n log n)
• Understand Dijkstra's algorithm for shortest path
• Know A* formula: f(n) = g(n) + h(n)
• Compare algorithms using Big O notation
• Know when to use each algorithm based on data characteristics