Pseudocode is an informal, language-independent description of an algorithm's logic. It uses structured English with programming constructs but doesn't need to compile. OCR H446 uses a specific pseudocode style in the exam.
// Variables and assignment
x ← 5
name ← "Alice"
// Input / Output
x ← userinput
print(x)
// Selection
if x > 0 then
print("positive")
elseif x < 0 then
print("negative")
else
print("zero")
endif
// Count-controlled loop
for i ← 1 to 10
print(i)
next i
// Condition-controlled loop
while x > 0
x ← x - 1
endwhile
// Subroutine (function)
function square(n)
return n * n
endfunction
result ← square(5) // result = 25
// 1D array (0-indexed)
scores ← [10, 20, 30, 40, 50]
print(scores[0]) // 10
// Iterating
for i ← 0 to length(scores) - 1
print(scores[i])
next i
// 2D array
grid ← [[1,2,3],[4,5,6],[7,8,9]]
print(grid[1][2]) // 6 (row 1, column 2)
A trace table (dry run) is a manual step-by-step execution of an algorithm, recording the value of each variable at each step. Used to check correctness, find bugs, and answer exam questions.
total ← 0
for i ← 1 to n
total ← total + i
next i
print(total)
| Step | i | total | Output |
|---|---|---|---|
| total ← 0 | 0 | ||
| i ← 1 | 1 | ||
| total ← 0+1 | 1 | ||
| i ← 2 | 2 | ||
| total ← 1+2 | 3 | ||
| i ← 3 | 3 | ||
| total ← 3+3 | 6 | ||
| i ← 4 | 4 | ||
| total ← 6+4 | 10 | ||
| i ← 5 | 5 | ||
| total ← 10+5 | 15 | ||
| print(total) | 15 |
Big O notation describes how an algorithm's time (or space) requirements grow as input size n increases. It expresses the worst-case upper bound, ignoring constants and lower-order terms.
| Notation | Name | Example | n=1000 approx. |
|---|---|---|---|
| O(1) | Constant | Array index lookup, hash table get | 1 operation |
| O(log n) | Logarithmic | Binary search | ~10 operations |
| O(n) | Linear | Linear search, single loop | 1,000 |
| O(n log n) | Linearithmic | Merge sort, heapsort | ~10,000 |
| O(n²) | Quadratic | Bubble sort, insertion sort (worst), nested loops | 1,000,000 |
| O(2ⁿ) | Exponential | Brute-force subset sum, naive Fibonacci | Astronomical |
| O(n!) | Factorial | Brute-force TSP | Impossible |
# O(1) — no loops, just assignments/comparisons
def get_first(arr):
return arr[0]
# O(n) — one loop through all elements
def linear_search(arr, target):
for item in arr: # n iterations
if item == target:
return True
return False
# O(n²) — nested loops, both depending on n
def bubble_sort(arr):
for i in range(len(arr)): # n
for j in range(len(arr)-i-1): # n
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
# O(log n) — halves the problem each step
def binary_search(arr, target):
low, high = 0, len(arr)-1
while low <= high: # log n iterations
mid = (low + high) // 2
if arr[mid] == target: return mid
elif arr[mid] < target: low = mid + 1
else: high = mid - 1
return -1
| Best case | Worst case | Average case | |
|---|---|---|---|
| Linear search | O(1) — target at index 0 | O(n) — target at end or absent | O(n/2) = O(n) |
| Binary search | O(1) — target is midpoint | O(log n) — search exhausted | O(log n) |
| Bubble sort | O(n) — already sorted (with flag) | O(n²) — reverse sorted | O(n²) |
| Merge sort | O(n log n) | O(n log n) | O(n log n) |
| Quick sort | O(n log n) — balanced pivots | O(n²) — already sorted, worst pivot | O(n log n) |
8 questions · 26 marks · instantly marked
max_value(arr) that returns the largest value in an array. Assume the array has at least one element.[4 marks]result ← 1
for i ← 1 to n
result ← result * i
next i
print(result)[5 marks]arr ← [3, 1, 4, 1, 5]
for i ← 0 to 3
for j ← 0 to 3 - i
if arr[j] > arr[j+1] then
temp ← arr[j]
arr[j] ← arr[j+1]
arr[j+1] ← temp
endif
next j
next i[4 marks]| Term | Definition |
|---|