Algorithms & Complexity
IB Syllabus: B2.4 — Algorithms and complexity
Table of Contents
- What Makes a Good Algorithm?
- Big O Notation
- Searching
- Sorting
- Comparing All Four
- HL Only: Recursion and Quicksort
- Quick Check
- Trace Exercises
- Practice Exercises
What Makes a Good Algorithm?
Any program can produce the correct answer. But two correct programs are not necessarily equal — one may be dramatically faster, especially on large inputs.
This section asks: how do we measure and compare algorithms? And which classic algorithms should every programmer know?
Big O Notation
Big O notation describes how an algorithm’s running time grows with input size (n). It expresses the worst-case growth rate, ignoring constants.
| Notation | Name | What it means |
|---|---|---|
| O(1) | Constant | Time does not change regardless of input size |
| O(log n) | Logarithmic | Time grows very slowly — doubles when input squares |
| O(n) | Linear | Time grows in proportion to input size |
| O(n²) | Quadratic | Time grows with the square of input size |
The key question: if the input doubles, what happens to the time?
- O(1): no change —
arr[500]is as fast asarr[0] - O(n): doubles — twice the elements, twice the steps
- O(n²): quadruples — twice the elements, four times the steps
- O(log n): barely increases — 1,000,000 elements needs only ~20 comparisons
Big O describes how the algorithm scales, not the exact number of steps. O(2n) and O(n) belong to the same class — the constant disappears at large n.
Searching
A search algorithm finds whether a target value exists in a collection, and if so, at which index.
Linear Search
Linear search checks every element from the beginning until the target is found or the array ends.
int[] numbers = {34, 67, 12, 72, 45};
int target = 72;
int foundIndex = -1;
boolean found = false;
for (int i = 0; i < numbers.length && !found; i++) {
if (numbers[i] == target) {
foundIndex = i;
found = true;
}
}
if (found) {
System.out.println("Found at index: " + foundIndex);
} else {
System.out.println(target + " not found.");
}
Trace: search for 72 in {34, 67, 12, 72, 45}
| i | numbers[i] | == 72? | found |
|---|---|---|---|
| 0 | 34 | No | false |
| 1 | 67 | No | false |
| 2 | 12 | No | false |
| 3 | 72 | Yes | true → stop |
foundIndex = 3
Complexity: O(n) — worst case visits every element (target not in array).
When to use: array is unsorted, or too small to justify sorting first.
Binary Search
Binary search eliminates half the remaining elements with each comparison. It requires the array to be sorted.
At each step: compare the target to the middle element.
- Equal → found
- Target smaller → search the left half
- Target larger → search the right half
int[] numbers = {12, 23, 34, 45, 67, 78, 89};
int target = 23;
int low = 0;
int high = numbers.length - 1;
int foundIndex = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (numbers[mid] == target) {
foundIndex = mid;
low = high + 1; // force loop to end
} else if (target < numbers[mid]) {
high = mid - 1; // search left half
} else {
low = mid + 1; // search right half
}
}
if (foundIndex != -1) {
System.out.println("Found at index: " + foundIndex);
} else {
System.out.println(target + " not found.");
}
Trace: search for 23 in {12, 23, 34, 45, 67, 78, 89}
| Step | low | high | mid | numbers[mid] | Decision |
|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 45 | 23 < 45 → high = 2 |
| 2 | 0 | 2 | 1 | 23 | Found → foundIndex = 1 |
Trace: search for 50 in {12, 23, 34, 45, 67, 78, 89} (not found)
| Step | low | high | mid | numbers[mid] | Decision |
|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 45 | 50 > 45 → low = 4 |
| 2 | 4 | 6 | 5 | 78 | 50 < 78 → high = 4 |
| 3 | 4 | 4 | 4 | 67 | 50 < 67 → high = 3 |
| 4 | low > high | — | — | — | Loop ends, not found |
Complexity: O(log n) — each comparison halves the search space.
Binary search only works on a sorted array. On an unsorted array, it produces wrong results without any error. Always confirm the array is sorted before applying binary search.
Sorting
A sorting algorithm rearranges elements into order. Sorting is a prerequisite for binary search.
Bubble Sort
Bubble sort compares adjacent pairs and swaps them if they are in the wrong order. Each full pass moves the largest unsorted element to its correct position at the end.
int[] arr = {64, 34, 25, 12, 22};
int n = arr.length;
for (int pass = 0; pass < n - 1; pass++) {
for (int i = 0; i < n - 1 - pass; i++) {
if (arr[i] > arr[i + 1]) {
// swap adjacent elements
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
// print sorted array
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
Trace: sort {64, 34, 25, 12, 22} — array after each pass:
| Pass | Array | Element fixed |
|---|---|---|
| Start | {64, 34, 25, 12, 22} | — |
| 1 | {34, 25, 12, 22, 64} | 64 |
| 2 | {25, 12, 22, 34, 64} | 34 |
| 3 | {12, 22, 25, 34, 64} | 25 |
| 4 | {12, 22, 25, 34, 64} | 22 |
Complexity: O(n²) — two nested loops, each up to n iterations.
In IB Paper 2, show the array after each pass, not each individual swap. Mark which element is in its final sorted position at the end of each pass.
Selection Sort
Selection sort scans the unsorted portion for the minimum element and places it at the front — one element per pass.
int[] arr = {64, 25, 12, 22, 11};
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// find the index of the minimum in arr[i..n-1]
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// swap the minimum into position i
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
Trace: sort {64, 25, 12, 22, 11} — array after each pass:
| Pass | Scanned | Min found (index) | Array after swap |
|---|---|---|---|
| 1 | entire array | 11 (index 4) | {11, 25, 12, 22, 64} |
| 2 | index 1–4 | 12 (index 2) | {11, 12, 25, 22, 64} |
| 3 | index 2–4 | 22 (index 3) | {11, 12, 22, 25, 64} |
| 4 | index 3–4 | 25 (index 3) | {11, 12, 22, 25, 64} |
Complexity: O(n²) — same number of comparisons as bubble sort, but only one swap per pass.
Bubble vs Selection
Both are O(n²) and taught for the same reason — they reveal how nested loops, comparisons, and swaps interact. The difference is what moves:
| Bubble sort | Selection sort | |
|---|---|---|
| What it does | Swaps adjacent pairs repeatedly | Finds minimum, swaps once per pass |
| Swaps per pass | Many | Exactly one |
| Best case | O(n) with early-exit optimisation | O(n²) — always scans everything |
Neither scales well to large data. They are studied to build reasoning about algorithm behaviour, not for real-world use.
Comparing All Four
| Algorithm | Best case | Worst case | Requires sorted? |
|---|---|---|---|
| Linear search | O(1) | O(n) | No |
| Binary search | O(1) | O(log n) | Yes |
| Bubble sort | O(n²) | O(n²) | — |
| Selection sort | O(n²) | O(n²) | — |
After covering methods (modularisation), it is natural to wrap these algorithms into reusable blocks —
linearSearch(arr, target),bubbleSort(arr). The logic stays exactly the same; only the packaging changes.
HL Only: Recursion and Quicksort
This section covers HL-only content (B2.4.4 and B2.4.5). SL students are not assessed on recursion or quicksort.
Recursion
A recursive method calls itself. Every recursive solution has two parts:
- Base case — the condition that stops the recursion
- Recursive case — calls itself with a smaller version of the problem
Without a base case, recursion never ends → stack overflow.
// Factorial: n! = n × (n-1) × ... × 1
// Base case: 0! = 1
public static int factorial(int n) {
if (n == 0) {
return 1; // base case
}
return n * factorial(n - 1); // recursive case
}
// Tracing factorial(4):
// factorial(4) → 4 * factorial(3)
// → 3 * factorial(2)
// → 2 * factorial(1)
// → 1 * factorial(0)
// → 1 (base case)
// Unwinds: 1 * 1 = 1, 2 * 1 = 2, 3 * 2 = 6, 4 * 6 = 24
Each call is pushed onto the call stack. When the base case is reached, calls return in reverse — unwinding the stack. This is the same call stack mechanism the OS uses to manage program execution.
// Fibonacci: F(n) = F(n-1) + F(n-2)
public static int fibonacci(int n) {
if (n <= 1) {
return n; // base cases: F(0)=0, F(1)=1
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
Limitation: fibonacci above makes duplicate recursive calls exponentially — its complexity is O(2ⁿ). This illustrates that recursion is not always the most efficient approach.
Quicksort
Quicksort is a divide-and-conquer algorithm. It selects a pivot, partitions the array so elements smaller than the pivot go left and larger go right, then recursively sorts each half.
public static void quicksort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quicksort(arr, low, pivotIndex - 1); // sort left partition
quicksort(arr, pivotIndex + 1, high); // sort right partition
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
}
int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp;
return i + 1;
}
// Initial call:
// quicksort(arr, 0, arr.length - 1);
Complexity:
- Average: O(n log n) — pivot splits the array roughly in half each time
- Worst: O(n²) — pivot is always the smallest or largest element (e.g. already-sorted input with last-element pivot)
Quick Check
Q1. What is the worst-case Big O complexity of binary search?
Q2. Binary search on the unsorted array {50, 12, 34, 7, 90} searching for 7 — what happens?
Q3. After the first pass of bubble sort on {5, 3, 8, 1, 4}, which element is guaranteed to be in its final sorted position?
Q4. Which statement correctly distinguishes bubble sort from selection sort?
Q5. An array grows from 100 to 200 elements. For an O(n²) algorithm, the work roughly:
Trace Exercises
Complete the trace tables. Type your answers into each cell, then click Check to see results.
Linear search — searching for 33 in {15, 8, 33, 72, 50}
Fill in each row as the loop runs. Write true or false for the found column.
| i | arr[i] | == 33? | found after this step |
|---|---|---|---|
| 0 | |||
| 1 | |||
| 2 |
What is foundIndex after the search?
Binary search — searching for 45 in {10, 20, 30, 40, 50, 60, 70}
Array indices: 0=10, 1=20, 2=30, 3=40, 4=50, 5=60, 6=70
| Step | low | high | mid | arr[mid] | Decision (write: left / right / found) |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
What is foundIndex? Was 45 found?
Bubble sort — sort {5, 3, 8, 1, 4} — write the full array after each pass
| Pass | arr[0] | arr[1] | arr[2] | arr[3] | arr[4] | Fixed at end |
|---|---|---|---|---|---|---|
| Start | 5 | 3 | 8 | 1 | 4 | — |
| 1 | ||||||
| 2 | 8 | |||||
| 3 | 5 | 8 | ||||
| 4 | 4 | 5 | 8 |
Practice Exercises
Trace
-
Trace a linear search for 33 in
{15, 33, 8, 72, 50}. Complete the table:i arr[i] == 33? found 0 1 … -
Trace a binary search for 45 in
{10, 20, 30, 40, 50, 60, 70}. Complete the table:Step low high mid arr[mid] Decision 1 0 6 -
Trace a binary search for 35 in
{10, 20, 30, 40, 50, 60, 70}— a value that is not in the array. Show all steps until the loop ends. -
Trace bubble sort on
{5, 3, 8, 1, 4}. Show the full array after each pass and circle the element placed in its final position. -
Trace selection sort on
{29, 10, 14, 37, 13}. For each pass, state the minimum found and its index, then show the array after the swap.
Understand
-
A binary search on a sorted array of 128 elements needs at most how many comparisons? What about 1024 elements? Explain using O(log n).
-
Why does binary search fail on an unsorted array? Give a concrete example with 5 elements where it produces a wrong result.
-
Bubble sort on
{1, 2, 3, 4, 5}(already sorted) — how many comparisons does it make? What does this tell you about its best-case behaviour? -
Both bubble sort and selection sort are O(n²). Give one reason you might prefer selection sort over bubble sort in a specific situation.
Write
-
Write the code to perform a linear search for a user-entered value in an array of 6 integers that the user also enters. Print either the index where it was found or a “not found” message.
-
Write the code to sort an array
{88, 42, 17, 65, 31}using selection sort, then print it. Trace the array state after each pass as comments in your code. -
An array
{3, 9, 15, 21, 27, 33, 39}is sorted. Write the binary search code to find a user-entered target. After the search, print how many comparisons were made. -
Challenge: Write a program that fills an array of 10 integers with random values (1–100 using
Random), prints the unsorted array, sorts it using bubble sort, prints the sorted array, then uses binary search to find a user-entered value.
HL Only
- Trace
factorial(3)— draw the call stack showing each push and pop. - Write a recursive method
power(int base, int exp)that returnsbaseraised toexp. Identify the base case and recursive case. Tracepower(2, 4). - Explain why the recursive Fibonacci implementation is inefficient. What is its Big O complexity and why?