B2.4 · Book pp. 358–377

Programming algorithms

Your level SL HL

Two programs can give the same answer, while one takes a second and the other takes a year. This section shows how to measure the difference.

What you need to know

Point	Content
B2.4.1	Describe efficiency using Big O notation
B2.4.2	Linear search and binary search
B2.4.3	Bubble sort and selection sort
B2.4.4	The concept of recursion
B2.4.5	Construct and trace recursive algorithms

⚠️ Common mistake

Many students sort with the wrong algorithm, or in the wrong direction. Read the question: selection sort in ascending order means exactly that.

Next: Big O →

B2.4.1 Big O notation

Time complexity describes how the number of steps grows with input size n, and space complexity describes how memory grows. Big O gives the upper bound on that growth, so it is used for the worst case.

To find it, keep the fastest-growing term and drop constants: 25n³ + n² + 7n is O(n³).

Order	Name	Example
O(1)	Constant	Reading list[i]
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear search
O(n log n)	Linearithmic	Quicksort, on average
O(n²)	Quadratic	Bubble and selection sort
O(2ⁿ)	Exponential	Plain recursive Fibonacci

n = 8
count = 0
for i in range(n):
    for j in range(n + 3):
        count = count + 1
print(count, "steps. That is n² + 3n, which is O(n²)")

✏️ Book correction

The book says adding up an array has O(n) space, because the sum “includes each value”. The sum is one variable. The extra space is O(1), and only the input itself takes O(n). Always say whether you are counting the input.

Next: searching →

B2.4.2 Searching

Linear search checks each element in turn. A conditional loop can stop early. Binary search checks the middle of sorted data, then discards the half that cannot hold the key.

numbers = [3, 9, 7, 4]
key = 7

position = -1
i = 0
while i < len(numbers) and position == -1:
    if numbers[i] == key:
        position = i
    i = i + 1

print(position)

numbers = [3, 4, 5, 7, 9, 11, 13]
key = 11

lower = 0
upper = len(numbers) - 1      # the last valid index
found = False

while lower <= upper and not found:
    mid = (lower + upper) // 2
    if numbers[mid] == key:
        found = True
    elif numbers[mid] < key:
        lower = mid + 1
    else:
        upper = mid - 1

print(mid if found else "not found")

✏️ Book correction: a real bug

The book sets upper = len(numbers). That index does not exist, so searching for a key larger than every element crashes with an IndexError. We ran it to check. Use len(numbers) - 1. The loop should also end when lower passes upper, not when “the end of the array is reached”.

Next: sorting →

B2.4.3 Sorting

Bubble sort compares adjacent values, and swaps those in the wrong order. Each pass fixes one more value at the end. Selection sort finds the smallest unsorted value, and swaps it to the front of the unsorted part.

numbers = [7, 3, 2, 9]
n = len(numbers)
swapped = True

while n > 1 and swapped:
    swapped = False
    n = n - 1
    for i in range(n):
        if numbers[i] > numbers[i + 1]:
            temp = numbers[i]
            numbers[i] = numbers[i + 1]
            numbers[i + 1] = temp
            swapped = True

print(numbers)

numbers = [9, 7, 2, 3]

for i in range(len(numbers) - 1):
    smallest = i
    for j in range(i + 1, len(numbers)):
        if numbers[j] < numbers[smallest]:
            smallest = j
    temp = numbers[i]
    numbers[i] = numbers[smallest]
    numbers[smallest] = temp

print(numbers)

✏️ Book correction: a real bug

The book’s conditional bubble sort loops over range(0, n-1) after reducing n, so it skips the last pair of each pass. Its example works by luck. Given [3, 2, 1] it returns [2, 3, 1]. Use range(n), as above.

Algorithm	Time	Extra space	Note
Linear search	O(n)	O(1)	Works on unsorted data
Binary search	O(log n)	O(1)	Data must be sorted
Bubble sort	O(n²)	O(1)	Can stop early with a swapped flag
Selection sort	O(n²)	O(1)	Few swaps, but no early exit

Next: recursion →

Next: review →

HL B2.4.4 Recursion

A recursive function calls itself on a smaller version of the problem.

Base case: a non-recursive stopping point.
General case: the call that moves towards the base case.
Winding: calls build up until the base case.
Unwinding: results return, from the last call back to the first.

def factorial(n):
    print("  " * (5 - n) + f"winding: factorial({n})")
    if n <= 1:            # base case
        return 1
    result = n * factorial(n - 1)     # general case
    print("  " * (5 - n) + f"unwinding: {result}")
    return result

print(factorial(5))

✏️ Book notes

The book’s unwinding is said to build “up towards the base case”. It moves away from the base case, back to the original call.
Its factorial stops only at n == 1, so factorial(0) never ends. Using n <= 1 is safer, and 0! is 1.

For recursion	Against recursion
Short, elegant code	Heavy stack use, with a risk of stack overflow
Suits trees, graphs and backtracking	Often slower, as each call has a cost
Splits problems naturally	Can be harder to follow and maintain

Next: recursive algorithms →

HL B2.4.5 Recursive algorithms

Fibonacci

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

for i in range(10):
    print(fib(i), end=" ")

This is short but O(2ⁿ), as it recalculates the same values. Try fib(35) to feel the cost.

Quicksort

Quicksort is divide and conquer. It picks a pivot, moves smaller values to the left and larger values to the right, then sorts each part. It averages O(n log n), with a worst case of O(n²).

def quick_sort(start, finish, numbers):
    if start >= finish:           # 0 or 1 items: already sorted
        return
    left = start
    right = finish
    pivot = numbers[(start + finish) // 2]

    while left <= right:
        while numbers[left] < pivot:
            left = left + 1
        while numbers[right] > pivot:
            right = right - 1
        if left <= right:
            temp = numbers[left]
            numbers[left] = numbers[right]
            numbers[right] = temp
            left = left + 1
            right = right - 1

    quick_sort(start, right, numbers)
    quick_sort(left, finish, numbers)

numbers = [16, 13, 4, 6, 22, 1, 9, 5]
quick_sort(0, len(numbers) - 1, numbers)
print(numbers)

✏️ Book correction: a real bug

The book’s Python version stops on start == finish. Partitions can end with start past finish, as its own trace shows, and the Python then recurses forever: we ran it, and got a RecursionError. Its Java version correctly uses start >= finish, as above.

Binary tree traversal

In-order: left, root, right.
Pre-order: root, left, right.
Post-order: left, right, root.

class Node:
    def __init__(self, value):
        self.data = value
        self.left = None
        self.right = None

def inorder(root):
    if root is None:
        return
    inorder(root.left)
    print(root.data, end=" ")
    inorder(root.right)

root = Node(5)
root.left = Node(3)
root.right = Node(8)
root.left.left = Node(2)
root.left.right = Node(4)
root.right.left = Node(7)
root.right.right = Node(9)

inorder(root)
print()
# Now write preorder (root, left, right) and postorder (left, right, root).

Next: review →

Quick quiz

1. Big O describes…

2. n² + 3n simplifies to…

3. Two nested loops, each to n, are…

4. Which is fastest for huge n?

5. Binary search needs…

6. Most comparisons for binary search in 1,000 items?

7. After one bubble sort pass…

8. Selection sort repeatedly…

HL Extra questions

1. A base case…

2. Each recursive call uses…

3. Quicksort’s average time is…

4. In-order traversal is…

Exam-style questions

These are written for this site in the style of Paper 2. Answer on paper first, then open the mark points.

State the list after two passes of selection sort on 3, 1, 7, 2, 4, 1, 6. [1]
Mark points
- 1, 1, 7, 2, 4, 3, 6 [1]
Construct a linear search that returns the position of key in a list, or −1. [4]
Mark points
- Loop through each index [1].
- Compare the element with key [1].
- Return the index on a match [1].
- Return −1 after the loop [1].
Explain why an O(n) algorithm is not always slower than an O(log n) one. [3]
Mark points
- Big O shows growth, not actual speed [1].
- Constants are ignored, so the O(log n) step could be costlier [1].
- So for small n, the O(n) algorithm may be faster [1].
A school with 1,500 students searches sorted IDs often. Justify using a binary search. [3]
Mark points
- Data is already sorted [1].
- It halves the search each time, at about 11 comparisons [1].
- Linear search could need 1,500 [1].
Compare bubble sort and selection sort. [3]
Mark points
- Both are O(n²) time and O(1) space [1].
- Selection sort makes fewer swaps [1].
- Bubble sort can stop early when no swaps occur [1].

HL Extra exam questions

Construct a recursive function to sum the numbers from 1 to n. [4]
Mark points
- A function with parameter n [1].
- Base case: if n == 1, return 1 [1].
- General case: return n + total(n − 1) [1].
- The call reduces n towards the base case [1].
State one advantage and one disadvantage of recursion over iteration. [2]
Mark points
- Shorter, more elegant code for tree-like problems [1].
- Uses more memory, with a risk of stack overflow [1].
Outline how quicksort works. [3]
Mark points
- Choose a pivot [1].
- Partition: smaller values go left, and larger values go right [1].
- Apply quicksort recursively to each part [1].