B2.4 Programming algorithms

Algorithmic efficiency and Big O notation

Why efficiency is measured by counting steps

Two programs that solve the same problem correctly can still differ greatly in how much time and memory they use. Measuring that difference with a stopwatch is unreliable: the same program runs faster on a new laptop than on an old phone, slower when other programs are busy, and at different speeds in Python and Java. A fairer measure counts the basic steps an algorithm performs, such as comparisons, assignments and swaps, and asks how that count changes as the input gets bigger.

The size of the input is written $n$. For a search, $n$ is the number of items in the list; for a sort, the number of items to be sorted; for a program that reads a file, the number of lines. Efficiency is then described as a relationship between $n$ and the work done, in two separate dimensions.

Time complexity ignores the actual seconds taken. If one algorithm does $n$ comparisons and another does $n^{2}$, the second slows down far more as $n$ grows, whatever the hardware. Memory use is described the same way.

A sort that rearranges a list inside the list it was given needs only a few extra variables, however long the list is. A sort that copies the data into a second list of the same length needs extra memory proportional to $n$. Both may take the same time, but the second uses far more memory on a large data set.

Counting steps in code

The function count_comparisons contains a nested loop in which the inner loop starts one place after the outer loop's current position. It counts how many times the inner loop body runs for three sizes of $n$, the same pattern of work that comparing every item in a list with every later item produces.

The output shows two things. When $n$ is multiplied by 10, the count is multiplied by about 100, so the work grows with the square of $n$. The exact count is $\frac{n(n-1)}{2}$, always a little less than half of $n^{2}$, because the inner loop runs $n-1$ times, then $n-2$, down to 0:

For $n = 1000$ that is $\frac{1000 \times 999}{2} = 499\,500$, matching the program.

Big O notation

An exact formula such as $\frac{1}{2}n^{2} - \frac{1}{2}n$ is more detail than is needed to compare algorithms. As $n$ becomes large, the $n^{2}$ term dominates: at $n = 1000$ the $\frac{1}{2}n$ term contributes only 500 out of 499,500. The constant $\frac{1}{2}$ does not change the shape of the growth either, since doubling $n$ still multiplies the work by four. Big O notation keeps only the part that decides the shape.

Big O is an upper bound on growth: it says the work grows no faster than the stated function once $n$ is large. It does not give a time in seconds, and it does not say that an $O(n)$ algorithm is faster than an $O(n^{2})$ one for every input; for very small $n$, an algorithm with a worse Big O but less work per step can win. What Big O guarantees is that, as $n$ keeps growing, the algorithm with the slower-growing function eventually wins and keeps winning by more.

Three rules turn a step count into Big O notation:

1. Keep only the fastest-growing term. $n^{2} + 5n + 20$ becomes $n^{2}$, because the other terms become negligible as $n$ grows.

2. Drop constant multipliers. $3n$ becomes $n$, and $\frac{1}{2}n^{2}$ becomes $n^{2}$. The constant depends on the language and the machine; the shape does not.

3. A fixed number of steps, however many, is $O(1)$. Five assignments or five hundred are both constant, because neither number depends on $n$.

Best, average and worst case

For many algorithms the number of steps depends on the particular data as well as on $n$. A search through a list of 1,000 names might find its target at the first position or not at all. Three cases describe this spread.

The best case is rarely used to choose an algorithm, because a program cannot rely on always receiving its most convenient input. It does show when an algorithm can finish early, which matters for data that is often already in order.

The average case describes typical behaviour on random data. For many algorithms it has the same Big O as the worst case, only with a smaller constant: a linear search for an item that is present checks about half the list on average, $\frac{n}{2}$ items, which is still $O(n)$.

The worst case is the usual basis for comparison because it is a guarantee: whatever data arrives, the algorithm will not do more work than this. A system that must always respond quickly, such as a cash machine checking a card or a game redrawing the screen sixty times a second, is designed around its worst case.

The common complexity classes

A small number of growth patterns appear again and again. Each has a name, and each comes from a recognisable shape of code.

Reading the element at a known index of an array is $O(1)$: the address is calculated directly from the index, so element 5 and element 5,000,000 take the same time. Adding two numbers, swapping two elements and returning a value are also $O(1)$.

The next class needs one piece of mathematics. A logarithm answers the question "how many times must a number be halved to get down to 1?" For $n = 16$, the halvings are 16, 8, 4, 2, 1: four halvings, so $\log_{2} 16 = 4$.

When $n$ is not a power of 2 the logarithm is not a whole number: $\log_{2} 1000 \approx 9.97$ and $\log_{2} 1\,000\,000 \approx 19.93$. Logarithms grow extremely slowly. Doubling $n$ adds only 1 to $\log_{2} n$, so a million items need only about 20 halvings and a billion about 30.

In Big O notation the base of the logarithm is not written, because changing the base only multiplies the value by a constant. The base is still 2 whenever the data is halved.

A single loop that visits every element once, such as a traversal that totals a list or finds its largest value, is $O(n)$. Linear time is the best possible for any task that must look at every item at least once.

$O(n \log n)$ appears when an algorithm does about $n$ steps of work at each of about $\log_{2} n$ levels, for example by repeatedly splitting a list in half and doing a linear amount of work on every level. It grows only a little faster than linear time.

Two nested loops that each run up to $n$ times give $O(n^{2})$, as count_comparisons showed. Bubble sort and selection sort are quadratic. Ten times more data means a hundred times more work, which is why quadratic algorithms become impractical for large data sets.

Exponential algorithms are only usable for very small inputs. An algorithm that tries every possible subset of $n$ items does $2^{n}$ steps: $2^{10} = 1024$ is fine, but $2^{60}$ steps at a billion steps per second would take about 37 years. A recursive function that calls itself twice for each value, such as the naive Fibonacci function in the HL section on recursion, grows in this way.

The growth curves show the classes together. For small $n$ they are close; as $n$ grows they separate quickly.

The table gives the step counts for three sizes of input. The last column assumes, for illustration, a computer that performs one step per microsecond (a million steps per second).

Calculating Big O from code

Big O can be read from the structure of the code without counting every step. The rules work from the inside out.

Loops in sequence add their costs, and the larger term wins. Loops that are nested multiply their costs. A loop that calls a subprogram multiplies its own count by the cost of that call: calling an $O(n)$ linear search inside a loop that runs $n$ times gives $O(n^{2})$.

The halving rule needs a closer look, because the loop is easy to misread as linear. The loop in halvings divides n by 2 with integer division until it reaches 1 and counts the passes.

The program prints 4 9 19: the loop runs $\lfloor \log_{2} n \rfloor$ times, so it is $O(\log n)$. Java's / on two int values already performs integer division, which Python writes as //.

Space complexity in practice

Space complexity counts only the extra memory an algorithm needs while it runs, not the memory already holding its input. The rules are the same as for time: a fixed number of extra variables is $O(1)$; an extra list that grows with the input is $O(n)$; an extra two-dimensional grid of $n$ by $n$ values is $O(n^{2})$.

Time and space often trade against each other. Storing extra data, such as an index or a copy sorted in a different order, can make searches faster at the cost of memory. On a device with little memory, such as a sensor or a smartwatch, an $O(1)$-space algorithm can be the right choice even when a faster one exists.

Scalability and choosing an algorithm

Scalability is the ability of a system to keep working well as its load grows. For an algorithm, the load is $n$, and Big O predicts what happens when $n$ increases: an $O(n)$ algorithm handles ten times more data with ten times more work, an $O(n^{2})$ algorithm needs a hundred times more, and an $O(\log n)$ algorithm needs only a few more steps. Choosing an algorithm therefore means asking how large $n$ will become, not only how fast the program runs on today's test data.

Several factors decide the choice besides the Big O of the worst case:

• The size of the data. For a list of 20 items any algorithm finishes instantly, so the simplest correct one is the best choice. For millions of items the growth rate dominates.

• The state of the data. Some algorithms need sorted data (binary search) and some run much faster on data that is already nearly in order (bubble sort with an early exit).

• How often the task runs. Sorting a list once so that it can then be searched thousands of times is worth the cost; sorting it to perform a single search is not.

• Memory limits. An algorithm that needs $O(n)$ extra memory may not fit on a small device.

• Simplicity. A simple algorithm is easier to write correctly, test and maintain, which matters when its speed is good enough.

Searching: linear search and binary search

A search algorithm looks for a target value in a collection and reports where it is, usually by returning its index, or reports that it is absent. By convention a search that fails returns -1, a value that can never be a valid index. Both search algorithms work on a one-dimensional array in Java or a list in Python, and both are written without the built-in tools that would do the job in one line: Python's in operator and index method, and Java's contains, indexOf and Arrays.binarySearch.

Linear search

The simplest way to find something is to look at every item in turn, starting from the first, until the target turns up or the items run out.

Linear search makes no assumptions about the data. The list can be in any order, can contain repeated values, and can hold any data type that can be compared for equality. The diagram of a linear search for the value 5 shows each comparison in turn.

The function linear_search returns the index of the first element equal to target, or -1 if there is none. The Python version keeps its own index counter instead of using len, so it works without that built-in.

The program prints 3 (the index of 5) and then -1 (8 is not in the list). The return -1 statement sits after the loop: it is reached only when every element has been checked without a match. In Java, items.length is a field of the array that stores its length, not a method that counts the elements.

A trace table records the search step by step, with one row for each pass of the loop. For linear_search(scores, 5):

Some programmers prefer a search with a single exit point at the end of the subprogram. That version uses a conditional loop that stops as soon as a Boolean flag called found becomes true, or when the index passes the last element.

Both versions give the same results and have the same efficiency. The test index < items.length in the while condition is what stops a failed search: without it, the body would go on to read items[5] in a five-element array, and Java would throw an ArrayIndexOutOfBoundsException exception (Python an IndexError).

Efficiency of linear search

The work done by a linear search is the number of comparisons with the target.

• Best case: the target is the first element. One comparison, whatever the length of the list: $O(1)$.

• Worst case: the target is the last element or is not in the list at all. Every one of the $n$ elements is compared: $O(n)$.

• Average case: if the target is present and equally likely to be at any position, the search checks about $\frac{n+1}{2}$ elements on average. Dropping the constant gives $O(n)$.

The space complexity is $O(1)$: the search needs only the index variable and, in the second version, the flag, however long the list is. Because the work grows in direct proportion to $n$, a list ten times longer takes ten times longer to search in the worst case.

Binary search

Finding a name in a printed phone book by linear search would mean reading from "Aaron" onwards. Nobody does this, because the book is in alphabetical order: opening it near the middle shows at once which half holds the name, and the other half can be ignored. Repeating the step on the remaining half finds any name in a few dozen openings at most.

The algorithm keeps two indexes, low and high, marking the first and last positions of the part of the list that might still contain the target. At each step it calculates the middle position mid and compares the element there with the target:

1. Set low to 0 and high to the last index, $n - 1$.

2. While low is less than or equal to high:

   1. Set mid to $(\text{low} + \text{high})$ divided by 2, rounded down.

   2. If the element at mid equals the target, return mid.

   3. If the element at mid is less than the target, the target can only be to its right: set low to mid + 1.

   4. Otherwise the target can only be to its left: set high to mid - 1.

3. If the loop ends because low has passed high, the target is not in the list: return -1.

The flowchart of binary search shows the same steps with the standard symbols from subtopic B1.1, Approaches to computational thinking. A flowchart describes an algorithm without tying it to either programming language.

The diagram of a search for 42 in a list of 11 sorted codes shows the part still being searched shrinking at each step.

The function binary_search follows the steps exactly. It assumes items is sorted in ascending order.

The program prints 6 and then -1. Python's // rounds the midpoint down; Java's / on two integers does the same. The Java version calculates the midpoint as low + (high - low) / 2, which always gives the same value as (low + high) / 2 for valid indexes but avoids an overflow bug that affected real libraries for years.

The trace table for binary_search(codes, 42) has one row per pass of the loop:

Three comparisons were needed; a linear search would have needed seven.

Why every detail of the loop matters

Binary search is short, but small changes break it. Each detail has a reason:

• low <= high, not low < high. When low equals high, one element is left and it still has to be checked. With <, a search for the last remaining candidate (such as 89 in codes) would stop one comparison early and wrongly return -1.

• low = mid + 1 and high = mid - 1, not low = mid or high = mid. The element at mid has already been checked, so it is excluded. Setting low = mid can leave low and mid unchanged forever when high = low + 1, an infinite loop.

• high = len(items) - 1, not len(items). Indexes run from 0 to $n - 1$. Starting high at $n$ lets mid reach $n$ and read past the end of the list.

• Integer division for mid. An index must be a whole number. In Python, / gives a float such as 5.0, which cannot be used as an index.

Efficiency of binary search

Every pass of the loop either finds the target or halves the number of candidates. Starting from $n$ elements, after one comparison about $\frac{n}{2}$ remain, after two about $\frac{n}{4}$, and after $k$ comparisons about $\frac{n}{2^{k}}$. The search must end once fewer than one element remains, so the largest number of comparisons is the number of halvings that take $n$ down to 1, plus one for the final check:

• Best case: the target is at the first middle position. One comparison: $O(1)$.

• Worst case: the target is found on the last possible comparison or is absent: $\lfloor \log_{2} n \rfloor + 1$ comparisons, $O(\log n)$.

• Average case: also $O(\log n)$, only about one comparison fewer than the worst case, because half of all positions are reached only on the last comparison.

• Space: $O(1)$ for the loop version (three index variables). The recursive version for HL uses $O(\log n)$ memory for its stack frames.

Searching a sorted list with an entry for every person on Earth would need at most 33 comparisons. The graph compares the worst-case comparisons of the two searches.

Case study: the binary search midpoint bug

Binary search looks so simple that a bug in it lay unnoticed in famous code for decades. Jon Bentley's book Programming Pearls (1986) presented a binary search that he had proved correct and tested. Joshua Bloch, who wrote the binary search in Java's standard library (java.util.Arrays) using the same approach, reported in 2006 that both contained the same bug: the Java version had been "lying in wait for nine years or so" until it broke a real program.

The fault was the line int mid = (low + high) / 2;. A Java int holds values only up to $2^{31} - 1 = 2\,147\,483\,647$. In an array of more than about a billion ($2^{30}$) elements, low and high can both be large enough for their sum to exceed that limit. The sum then suffers integer overflow and wraps round to a negative number, so mid becomes negative and reading items[mid] throws an ArrayIndexOutOfBoundsException. The program Midpoint shows the effect with two large values.

The Java program prints -397483648 and then 1750000000; the Python version prints 1750000000 twice. The two languages differ because a Python int grows to whatever size a value needs and never overflows, while a Java int has a fixed 32 bits. The usual fix, low + (high - low) / 2, never forms the large sum: high - low is at most the length of the array, so the result always fits.

Source: Joshua Bloch, “Extra, Extra – Read All About It: Nearly All Binary Searches and Mergesorts are Broken”, Google Research Blog, 2 June 2006.

The case shows three things. An algorithm can be correct while its implementation is wrong, because the code runs on real hardware with fixed-size integers that the mathematical version ignores. Bugs that appear only at extreme sizes are hard to find by ordinary testing, which uses small inputs; this one needed arrays far larger than any computer of 1986 could hold. Choosing data types is part of choosing an algorithm: the same line is safe in Python and dangerous in Java.

Choosing between linear search and binary search

Binary search is far faster on large data, but it is not always the right choice. Its requirement for sorted data has a cost, and for some data it is impossible.

Sorting data first so that it can be searched costs $O(n \log n)$ with an efficient sort, more than a single linear search's $O(n)$. Sorting is worth it only when the data will be searched many times, or when it is kept sorted anyway, as a database index is.

A printed phone book shows both sides of the choice. Its entries are sorted by surname, so finding a person's number from their name is a binary-search problem. Finding whose number 555 0193 is means a linear search through every entry, because the book is not sorted by number. A program in the same position has two options: search linearly, or keep a second copy of the data sorted by number (more memory and more work on every update) so that binary search can be used for both questions.

Sorting: bubble sort and selection sort

Sorted data is easier for both people and programs to use. A sorted list can be searched with binary search, its smallest and largest values are at the ends, duplicates sit next to each other, and a report in order of date or score is easier to read.

Bubble sort and selection sort are built from two operations: comparing two elements, and exchanging them when they are in the wrong order.

A swap needs three assignments. Writing items[0] = items[1] first would overwrite the value at index 0 before it had been saved, so the old value is copied into temp first.

The output is [3, 6, 8]. Python also allows items[0], items[1] = items[1], items[0], which swaps in one line; the three-line version works in both languages and shows exactly what happens.

Both sorts also share two properties that describe how a sorting algorithm uses memory and treats equal values.

Bubble sort and selection sort are both in place: they rearrange the list they are given using one temporary variable and a few counters. The built-in sorted function in Python is not, because it builds and returns a new list.

Stability matters when records are sorted by one field after another. If a class list is first sorted by name and then sorted by grade with a stable sort, students with the same grade stay in alphabetical order. An unstable sort may mix them up.

Bubble sort

Bubble sort repeatedly walks along the list comparing each pair of neighbouring elements and swapping any pair that is in the wrong order. On each walk, the largest unsorted value is carried along by successive swaps until it reaches its final place at the end, like a bubble rising to the surface.

Each walk along the list has its own name.

After the first pass of bubble sort, the largest value is at the end. After the second pass, the two largest are in place, and so on. A list of $n$ elements therefore needs at most $n - 1$ passes, and each pass can stop one position earlier than the one before, because the end of the list is already sorted. The diagram of bubble sort on [6, 3, 8, 2, 5] shows the list after each pass.

The basic version uses a counted loop for the passes and a nested counted loop for the comparisons. The inner loop runs to n - 1 - p, so it never compares into the sorted part and never reads past the end.

The program prints [2, 3, 5, 6, 8]. The function returns nothing: it changes the list it was given. In both languages a list or array is passed to a subprogram as a reference, so the caller's heights is the list that gets sorted.

The basic version always makes all $n - 1$ passes, even when the list became sorted early. If a whole pass makes no swaps, every adjacent pair is in order and the list is sorted, so the algorithm can stop. The improved version records this with a flag called swapped and uses a conditional loop for the passes.

Tracing bubble sort

A full trace of a sort records every comparison. For pass 1 of the improved version on [6, 3, 8, 2, 5]:

At the start of each pass swapped is reset to False; it becomes True at the first swap of the pass. Pass 4 makes no swap, so swapped stays False and the while loop ends. In total the sort made 10 comparisons and 6 swaps. A shorter pass-by-pass table, with the list after each pass, is often enough when a question asks only for the state of the list:

Efficiency of bubble sort

The number of comparisons in pass 1 is $n - 1$, in pass 2 $n - 2$, down to 1 in the last pass. In the worst case, a list in reverse order, every pass is needed and every comparison leads to a swap:

• Worst case: reverse order. $\frac{n(n-1)}{2}$ comparisons and the same number of swaps: $O(n^{2})$.

• Average case: random order. About the same number of comparisons and about half as many swaps: still $O(n^{2})$.

• Best case (improved version): already sorted. The first pass makes $n - 1$ comparisons and no swaps, so the loop stops: $O(n)$. The basic version without the flag makes all $\frac{n(n-1)}{2}$

• Space: $O(1)$; bubble sort is in place.

• Stability: stable, because it swaps only when items[j] > items[j + 1], never when two values are equal, so equal values never pass each other.

Bubble sort's reputation is poor. Donald Knuth wrote in The Art of Computer Programming that it "seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems". When Google's chief executive Eric Schmidt asked the presidential candidate Barack Obama in a 2007 interview how to sort a million integers, Obama answered: "I think the bubble sort would be the wrong way to go." For a million integers in random order, bubble sort needs about $5 \times 10^{11}$ comparisons.

Selection sort

Selection sort builds the sorted list from the left. On each pass it searches the unsorted part for the smallest value and swaps it into the first unsorted position. After pass 1 the smallest value is at index 0, after pass 2 the second smallest is at index 1, and so on.

The diagram of selection sort on the same list, [6, 3, 8, 2, 5], shows the sorted part growing from the left.

Finding the minimum is itself a small algorithm: assume the first unsorted element is the smallest, then compare it with each later element and remember the index of any smaller one. Selection sort repeats this for each position. The code finds the minimum itself instead of calling Python's min or Java's Collections.min.

The program prints [2, 3, 5, 6, 8]. The test if min_index != i skips a pointless swap of an element with itself; the sort is still correct without it, but it would then always make exactly $n - 1$ swaps.

Tracing selection sort

The trace table records min_index as the inner loop moves through the unsorted part. For [6, 3, 8, 2, 5]:

The sort made 10 comparisons and 2 swaps: the same number of comparisons as bubble sort on this list, but a third of the swaps.

Efficiency of selection sort

Pass 1 compares the first element's candidate with the other $n - 1$ elements, pass 2 makes $n - 2$ comparisons, and so on. Unlike bubble sort, selection sort has no way to finish early: it cannot know that the rest of the list is in order without scanning it for the minimum. Every input of size $n$ therefore costs exactly

• Best, average and worst case: $\frac{n(n-1)}{2}$ comparisons, $O(n^{2})$, even on a list that is already sorted.

• Swaps: at most one per pass, so at most $n - 1$: $O(n)$. On sorted data it makes none.

• Space: $O(1)$; selection sort is in place.

• Stability: not stable in this array form. A swap can jump an element over others with the same key: sorting the records (Ana, 4), (Ben, 4), (Cy, 1) by grade swaps (Cy, 1) with (Ana, 4) on the first pass, giving (Cy, 1), (Ben, 4), (Ana, 4), so Ana and Ben change order.

The small number of swaps is selection sort's one real advantage. When writing to memory is much more expensive than reading, as with flash memory, where every write wears the cells a little, or when each element is a large record that is slow to move, $n - 1$ swaps instead of up to $\frac{n(n-1)}{2}$ can matter more than the comparisons.

Comparing bubble sort and selection sort

Both algorithms are quadratic in the worst case and use constant extra memory, so on large data sets both are slow. They differ in how they respond to the starting order of the data and in how many writes they make.

Counting the operations on real runs of the two Python functions shows how the starting order changes the picture. The "nearly sorted" lists have one pair of neighbouring values exchanged.

Counts from the two Python functions with counters added for comparisons and swaps; each random list is one run with a fixed seed.

The counts lead to a clear evaluation. On sorted or nearly sorted data, bubble sort with a flag is far faster, finishing in one or two passes, while selection sort still makes every comparison. On random or reverse-ordered data both make about the same number of comparisons, but bubble sort makes hundreds of times more swaps on the large lists, so selection sort usually runs faster. On a reverse-ordered list selection sort makes only $\frac{n}{2}$ swaps, because each swap puts two values in their final places. For lists of a few dozen items the difference is unimportant, and both are easy to write correctly.

The graph compares the comparison counts as $n$ grows. Selection sort follows the quadratic curve for every input; bubble sort follows it for random and reversed data but drops to the straight line on sorted data.

What the built-in sorts do

Python's sorted and list.sort, and Java's Arrays.sort and Collections.sort, are not bubble or selection sorts. Python used Timsort, written by Tim Peters in 2002, from version 2.3 until version 3.11 replaced it with a closely related algorithm called Powersort; Java SE 7 adopted Timsort for sorting arrays of objects, and Android uses it too. Timsort is a hybrid of insertion sort and merge sort that finds runs of data already in order and merges them, giving $O(n \log n)$ in the worst case and close to $O(n)$ on nearly sorted data. For arrays of primitive values such as int[], Java's Arrays.sort uses a dual-pivot quicksort.

Sources: Wikipedia, “Timsort”; Oracle, Java SE 21 API documentation for java.util.Arrays.

The built-ins are the right choice in real programs. Bubble sort and selection sort are studied because they are simple enough to write, trace and analyse by hand, and because they show clearly what makes an algorithm quadratic.

Recursion (HL only)

Solving a problem with a smaller copy of itself

Some problems contain smaller versions of themselves. The factorial of 4, written $4!$, is $4 \times 3 \times 2 \times 1 = 24$, but it can also be described as $4 \times 3!$: four times the factorial of a smaller number. In the same way $3! = 3 \times 2!$, $2! = 2 \times 1!$, and $1! = 1$ needs no further work. A subprogram can follow this description directly by calling itself.

Every correct recursive subprogram has two parts. The first stops the recursion.

For factorial, the base case is $n \le 1$, where the answer is 1. Without a base case, or with one the calls never reach, the subprogram would call itself forever. The second part does the self-reference.

The function factorial contains both parts, and factorial_loop computes the same value with a counted loop, for comparison.

Both lines of output show equal results: 24 24, then 2432902008176640000 2432902008176640000. The Java version returns a long, because $20!$ is far larger than the largest int; $21!$ would overflow even a long, while Python's integers simply grow.

A correct recursive subprogram needs a base case, recursive calls that move closer to it (here n - 1 is smaller than n), and a recursive case that uses the returned value (n * the result). Designing one is an example of algorithmic design: the programmer trusts that the call on the smaller problem returns the right answer and only has to decide how to combine it.

How recursion runs: the call stack

When factorial(4) calls factorial(3), the first call has not finished: it is waiting to multiply 4 by whatever comes back. The computer must remember that n was 4 in the first call while n is 3 in the second, and where to continue when the second call returns. It does this with a stack, the last-in, first-out structure from subtopic B2.2, Data structures.

The call stack is a different thing from a stack data structure that a program creates for itself, although both work in the same last-in, first-out way. Each entry on it has its own name.

Each call gets its own frame, so the n in factorial(4) and the n in factorial(3) are separate variables that do not interfere. The diagram of the call stack for factorial(4) shows the frames at the moment the base case is reached.

The process has two phases. In the winding phase, each call pushes a new frame, until the base case is reached with four factorial frames on the stack. Nothing has been multiplied yet. In the second phase the calls finish in reverse order.

During unwinding, factorial(1) returns 1 to factorial(2), which returns $2 \times 1 = 2$ to factorial(3), which returns $3 \times 2 = 6$ to factorial(4), which returns $4 \times 6 = 24$ to the main program. All the multiplications happen on the way back.

The call stack has a limited size. A recursion that is too deep, or has no reachable base case, pushes frames until the space runs out: a stack overflow, the same idea as pushing onto a full stack applied to subprogram calls. The function count_down has no base case.

The Python program prints 3, 2, 1, 0, −1 and onwards down to −995, 999 lines in all, then stops with an error:

CPython limits the depth of calls to 1,000 by default (sys.getrecursionlimit() returns 1000) and raises a RecursionError rather than letting the real stack overflow and crash the interpreter. Java has no fixed count: the JVM throws a StackOverflowError when the thread's stack memory is full. In test runs of NoBase with the default stack size, this happened after between about 42,000 and 46,000 calls; the depth depends on the stack size and on how much each frame holds, and varies between runs.

Source: Python documentation, sys.getrecursionlimit; runs with CPython 3.13 and OpenJDK 25.

Non-branching and branching recursion

The recursive subprograms so far make at most one recursive call each time they run, so the calls form a single chain.

A non-branching recursion that reduces $n$ by 1 each time makes $n$ calls and has $n$ frames on the stack at its deepest: $O(n)$ time and $O(n)$ space. Some problems split into two or more smaller problems instead.

The Fibonacci sequence 0, 1, 1, 2, 3, 5, 8, … is defined by $F(n) = F(n-1) + F(n-2)$, with $F(0) = 0$ and $F(1) = 1$. Written directly as code, each call makes two more calls. The function counts how many calls it makes; in Python the global statement is needed to change the variable calls from inside the function.

Computing $F(30)$ takes more than 2.6 million calls, because the same values are calculated again and again: fib(30) calls fib(28) once directly and again inside fib(29), and the repetition multiplies at every level. Each increase of $n$ by one multiplies the number of calls by about 1.6, so this function runs in exponential time, usually written $O(2^{n})$ as an upper bound. A loop that keeps the last two values computes $F(30)$ in 29 additions. The graph compares the calls made by this branching function with the $n$ calls of a non-branching one such as factorial.

Advantages and limitations of recursion

Anything that can be written recursively can also be written with loops, sometimes with an explicit stack data structure to replace the call stack. The choice is about clarity, efficiency and the shape of the problem.

The advantages are strongest for problems that branch. Visiting every node of a tree, drawing a fractal, or sorting by splitting a list into parts are short and natural with recursion and awkward with loops. For a simple chain such as factorial, a sum or a countdown, a loop is usually the better engineering choice: it is at least as clear, uses constant memory and cannot overflow the stack.

Divide and conquer and quicksort

Several of the fastest algorithms use the same strategy: split a problem into smaller independent problems of the same kind, solve each one recursively, then combine the results.

Binary search is a simple case: it divides the list, then continues in only one half, so it needs only non-branching recursion. Quicksort, developed by Tony Hoare in 1959 while he was a visiting student at Moscow State University and needed to sort Russian words for a machine translation project, divides a list and then sorts both parts. It was published in 1961.

The algorithm needs two further terms. The first is the value that everything is compared with.

The pivot can be any element: the first, the last, the middle, or a random one. Simple versions use the last element of the part being sorted. The rearrangement around it is the core of the algorithm.

After one partition the pivot never moves again, and no element ever needs to cross it. Quicksort then calls itself on the part to the left of the pivot and on the part to the right. A part with zero or one element is already sorted: that is the base case. The diagram of quicksort on [7, 2, 9, 4, 1, 8, 5] shows each level of the recursion.

The partition scheme in partition, often credited to Nico Lomuto, takes the last element as the pivot. Index i marks where the next element smaller than the pivot should go; index j scans the part from left to right. Hoare's original scheme scans inwards from both ends and makes fewer swaps, but is harder to follow. Reading the code is optional: the trace of partition and the diagram show everything the algorithm does, and quicksort is explained rather than written by hand.

The trace of the first call, partition(marks, 0, 6) on marks = [7, 2, 9, 4, 1, 8, 5] with pivot 5, shows how the small values collect at the left:

partition returns 3. Then quicksort(marks, 0, 2) sorts [2, 4, 1] and quicksort(marks, 4, 6) sorts [9, 8, 7], each by the same steps. Quicksort is branching recursion: each call that partitions can make two further calls, so the calls form a tree, as the quicksort diagram shows level by level.

Efficiency of quicksort

Each level of the recursion partitions all the elements still unsorted, which takes about $n$ comparisons per level. The number of levels depends on how evenly the pivots split the lists.

• Best and average case: the pivots split each list into two parts of roughly equal size, so the list is halved at each level and there are about $\log_{2} n$ levels. About $n$ comparisons on each of $\log_{2} n$ levels gives $O(n \log n)$.

• Worst case: each pivot is the smallest or largest element, so one part is empty and the other holds everything else. With the last element as pivot this happens on data that is already sorted or in reverse order. The levels then number $n$, with $n - 1$, $n - 2$, … comparisons: $\frac{n(n-1)}{2}$

• Space: quicksort partitions in place, but its recursive calls use the call stack: $O(\log n)$ frames deep on average, $O(n)$ in the worst case.

• Stability: not stable, because partitioning swaps elements over long distances.

Runs of the optional Python code, with counters added, show both behaviours. On 1,000 values in random order, quicksort made 11,508 comparisons with a deepest recursion of 22 calls, close to $1000 \log_{2} 1000 \approx 9966$. On 1,000 values already in order it made 499,500 comparisons, exactly $\frac{1000 \times 999}{2}$, and its recursion went 1,000 calls deep; that run needed a raised recursion limit, because with CPython's default limit the same call stops with a RecursionError. Library versions avoid the worst case by choosing the pivot more carefully, for example as the median of the first, middle and last elements, or at random.

Traversing binary trees

A binary tree is a recursive structure: each node holds a value and up to two smaller binary trees, its left and right subtrees. Processing the whole tree therefore follows the same pattern at every node. An in-order traversal of a binary search tree visits the left subtree, then the node itself, then the right subtree, and so produces the values in sorted order. The base case is an empty subtree, where there is nothing to visit.

Each node makes two recursive calls, one per subtree, so tree traversal is branching recursion. It shows recursion at its most useful: the recursive version is three lines long, while a loop version must manage its own stack of nodes still to visit. Subtopic B4.1 describes trees, their traversals and binary search trees in full.

Fractals

Recursion also produces images. A shape drawn by replacing each part of it with smaller copies of the whole, repeated at smaller and smaller scales, has the same structure as a recursive subprogram: the drawing step calls itself on each smaller piece, and a minimum size or a depth counter is the base case.

The Koch curve, described by the Swedish mathematician Helge von Koch in 1904, starts from a straight line segment. Each iteration divides every segment into three equal parts and replaces the middle third with two sides of an equilateral triangle pointing outwards, so each segment becomes four segments, each one-third as long. Three Koch curves on the sides of an equilateral triangle form the Koch snowflake.

The recursive structure leads to an unusual property. Every iteration multiplies the perimeter by $\frac{4}{3}$, so it grows without limit, while the added triangles become so small that the area approaches a fixed value, $\frac{8}{5}$ of the original triangle's area. A recursive drawing subprogram takes a segment and a depth: if the depth is 0 (the base case) it draws the segment; otherwise it calls itself four times on the four smaller segments with the depth reduced by 1. This is branching recursion, and a depth of $d$ produces $3 \times 4^{d}$ segments, so the work grows exponentially with the depth.

Source: Wikipedia, “Koch snowflake”.

Constructing and tracing recursive algorithms (HL only)

A method for writing a recursive subprogram

Writing a recursive subprogram is easier with a fixed sequence of four decisions:

1. Find the smallest version of the problem and its answer. This gives the base case: an empty list sums to 0; any number to the power 0 is 1; a string of length 0 or 1 is its own reverse.

2. Describe the problem using a smaller version of itself. The sum of a list is its first element plus the sum of the rest; $b^{e} = b \times b^{e-1}$; the reverse of a string is the reverse of everything after its first character, followed by that first character.

3. Make sure every call moves towards the base case. The index moves one place along the list; the exponent falls by 1; the string loses a character.

4. Return or use the result of the recursive call. The recursive case must return the combined value.

Three subprograms built this way are sum_list, power and reverse_text. To avoid copying the list at each step, sum_list takes the index of the first element still to add as a second parameter.

The output is 22, 81 and pool. Python's text[1:] and Java's text.substring(1) both give the string without its first character.

Tracing with a call table

A recursive trace records each call with its parameters, what it is waiting for, and what it finally returns. The calls are listed in the order they start (winding), and the return values are filled in from the bottom up (unwinding). For reverse_text("loop"):

Call 4 returns first, then call 3, then 2, then 1, the reverse of the order in which they started. The original call returns "pool". A call table with the "Returns" column filled in from the bottom row upwards is the clearest way to show unwinding.

Recursive search algorithms

Both searches can be written recursively. Binary search suits it well, because each step continues with only one half of the list: one recursive call, so it is non-branching. The part still being searched is passed in through the parameters low and high, and the base case low > high means that no elements remain.

The output is 6 and -1, the same as the loop version. The call table for the search for 42 has three calls, and the answer is passed back unchanged through each one:

The recursive version has the same $O(\log n)$ time as the loop, but uses $O(\log n)$ space for its stack frames instead of $O(1)$. For linear search, a recursive version (check items[index], otherwise search from index + 1) would need one frame per element, $O(n)$ space, and would fail with a RecursionError on any Python list of more than about 1,000 items: a clear case where the loop is the better design.

The function sum_to is meant to add the whole numbers from 1 to n, but its recursive case has no return.

The function mystery builds a string as the calls unwind. Its structure, a recursive call made before the current call adds its own part, means the results are assembled in reverse order.

The greatest common divisor (GCD) of two numbers has a short recursive definition found by Euclid: the GCD of a and b equals the GCD of b and the remainder of a divided by b, and the GCD of a and 0 is a.

The program prints 12. The calls are gcd(84, 36), gcd(36, 12) (because $84 \bmod 36 = 12$) and gcd(12, 0) (because $36 \bmod 12 = 0$), which is the base case and returns 12; the value is passed back unchanged through the other two calls. When the recursive call is the very last action and its result is returned unchanged, as here and in recursive binary search, the recursion can be rewritten as a simple while loop that updates the parameters.

Exam focus

Programming algorithms are examined on Paper 2, in the version of the paper for your language, Python or Java. Questions set the algorithm in a context (a list of scores, readings or product codes) and move through parts of rising demand:

• State a Big O value or the output of a search (1 mark each).

• Describe or calculate efficiency: count comparisons, read the Big O from loop structure, or explain why one algorithm scales better (2–4 marks).

• Trace a search or a sort in a trace table: low, high and mid for binary search; the list after each pass for a sort (3–5 marks). Marks go to correct rows in order, so show every change.

• Construct a search or sort, often "without using built-in functions" such as sort, sorted, max, min, index or in (4–6 marks). Marks are awarded for features: initialisation, loop bounds, the comparison, the swap or update, and the return value.

• Evaluate or compare algorithms for given data, such as bubble sort against selection sort on nearly sorted data, or linear against binary search (4–6 marks), with a justified conclusion.

The compulsory algorithmic-thinking question has no code: a search or sort may appear as a flowchart, as numbered steps, or as a process with cards or objects, to be traced or described in words. HL papers add recursion: construct a short non-branching recursive subprogram, trace a recursive call with a call table, explain limitations of recursion, or explain how quicksort sorts a given list.

The command term decides the shape of a "compare" or "evaluate" answer. Each point should name both algorithms and link a property to a consequence for the data in the question.

Binary search questions often hinge on a single row, the one where the loop ends.

The HL questions on recursion have their own routine.

Practice questions

1. State the worst-case time complexity of binary search and the best-case time complexity of selection sort. [2]

2. Explain why a binary search of a sorted list of 1,000,000 items needs at most 20 comparisons. [2]

3. Determine the time complexity of this Python fragment, where n is the size of the input, and justify your answer: for i in range(n): containing j = n and while j > 1: j = j // 2. [2]

4. Trace the basic bubble sort (no swapped flag) on [9, 4, 7, 1], giving the list after each pass and the number of swaps in each pass. [3]

5. Construct a function count_occurrences(items, target) (Java: countOccurrences(int[] items, int target)) that returns how many times target appears in items, without using built-in functions such as count. [3]

6. Compare linear search and binary search. [4]

7. Explain, using an example, why selection sort is not a stable sort. [3]

8. (HL only) Construct a recursive function count_char(text, ch) (Java: countChar(String text, char ch)) that returns the number of times the character ch appears in the string text. [4]

9. (HL only) The function show(n) is defined as: if n > 0, print "down" and n, call show(n - 1), then print "up" and n. State the output of show(3) and explain the order in terms of the call stack. [4]

10. (HL only) Explain why quicksort with the last element as the pivot takes $O(n^{2})$ time on a list that is already sorted, and suggest one way to avoid this. [4]