B2.4 Programming algorithms

Big O notation

Big O describes how the number of steps grows as the input size \(n\) grows, in the worst case, ignoring constants.

Doubling \(n\) doubles an \(O(n)\) algorithm's work but quadruples an \(O(n^2)\) one, and adds just one step to \(O(\log n)\).

Linear search

Check each item in turn. Works on unsorted data; worst case \(n\) comparisons.

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

Binary search

Only on sorted data. Compare with the middle item and discard the half that cannot contain the target.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Trace on [2, 5, 9, 14, 20, 27, 33, 41]:

Each step halves the range, so a million items need at most 20 comparisons (\(2^{20} \approx 10^6\)). The cost is that the data must be kept sorted.

Bubble sort

Compare neighbours and swap if out of order; after each pass the largest remaining value has "bubbled" to the end. [5, 2, 8, 1, 4] ascending:

def bubble_sort(a):
    n = len(a)
    for p in range(n - 1):
        swapped = False
        for i in range(n - 1 - p):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:
            break

The swapped flag ends early on sorted data (best case \(O(n)\)).

Selection sort

Find the smallest item in the unsorted part and swap it into the next position. [6, 3, 9, 2, 7]:

Always \(O(n^2)\) comparisons but at most \(n - 1\) swaps, fewer than bubble sort, which helps when writing to memory is expensive.

Recursion (HL)

A recursive function calls itself on a smaller version of the problem. It needs a base case that stops the calls and a recursive case that moves towards it.

def power(b, e):
    if e == 0:            # base case
        return 1
    return b * power(b, e - 1)

power(3, 3) -> 3 x power(3, 2) -> 3 x 3 x power(3, 1) -> 3 x 3 x 3 x power(3, 0) = 27. That is 4 calls. Each call waits on the call stack; without a base case the stack fills and the program crashes (stack overflow). Recursion gives short, elegant code for naturally self-similar problems (trees, divide and conquer) but uses more memory than a loop.

Quicksort (HL)

Choose a pivot, partition the rest into items smaller and larger than it, then quicksort each part.

def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = a[0]
    smaller = [x for x in a[1:] if x < pivot]
    larger = [x for x in a[1:] if x >= pivot]
    return quicksort(smaller) + [pivot] + quicksort(larger)

[4, 7, 1, 6, 2]: pivot 4 -> [1, 2] + 4 + [7, 6]; then [1, 2] -> [] + 1 + [2]; [7, 6] -> [6] + 7 + []. Result [1, 2, 4, 6, 7]. Average \(O(n \log n)\); worst case \(O(n^2)\) when the pivot is always the smallest or largest (for example, first-item pivot on already sorted data).

Common mistakes

• Using binary search on unsorted data.
• Computing mid with ordinary division instead of integer division.
• Showing only the final list when asked for each pass.
• Writing a recursive function whose recursive call does not move towards the base case.

Exam tips

• When evaluating searches, mention data size, whether it is sorted, and the cost of sorting it.
• Count comparisons and swaps separately if the question asks.
• For recursion traces, write each call on its own line and fill in returns from the bottom up.