IB Computer Science B2.4: Programming algorithms

New IB Computer Science syllabus · first exams May 2027 · Theme B · Paper 2 · SL & HL (B2.4.4 and B2.4.5 HL only) · Python and Java

B2.4 covers the classic algorithms you must be able to write and trace by hand, and how to judge their efficiency with Big O notation.

StatementTopicCommand term
B2.4.1Efficiency and Big O notationDescribe
B2.4.2Linear and binary searchConstruct / Trace
B2.4.3Bubble sort and selection sortConstruct / Trace
B2.4.4 (HL)Recursion: concept and applicationsExplain
B2.4.5 (HL)Recursive algorithmsConstruct / Trace

Key points

B2.4.1 Big O notation

  • Big O describes how running time (time complexity) or memory use (space complexity) grows as the input size n grows.
  • One pass over n items is O(n).
  • A loop nested inside another loop over the same data is O(n²).
  • Halving the search each step is O(log n).

B2.4.2 Searching

  • Linear search: checks each item in turn. It works on unsorted data and is O(n).
  • Binary search: needs sorted data. It checks the middle item and discards half each time, so it's O(log n).
  • Example from the guide: finding a phone number from a sorted list of names suits binary search. Finding a name from a number, in an unsorted list, needs linear search.

B2.4.3 Sorting

  • Bubble sort: repeatedly swaps adjacent items that are out of order. The largest item "bubbles" to the end on each pass.
  • Selection sort: repeatedly finds the smallest remaining item and swaps it into place.
  • Both are O(n²) time and O(1) extra space. Compare how efficient they are on different datasets.

B2.4.4–B2.4.5 Recursion (HL only)

  • A recursive function calls itself on a smaller version of the problem until it reaches a base case.
  • Suits: fractals, traversing binary trees, and sorting (quicksort).
  • Limits: extra memory for each call, and the risk of a stack overflow.
  • B2.4.5 requires simple, non-branching recursive code only.

Exam-style question

Construct and trace a binary search for the value 16 in the sorted list [4, 8, 16, 23, 42], showing low, high and mid at each step. [5]

Mark scheme

low = 0, high = 4, mid = 2, and values[2] = 16, so it's found immediately, returning 2.

  • [3] for the correct low, high and mid values.
  • [2] for correctly identifying the match on the first step.

Python

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

Java

public static int binarySearch(int[] values, int target) {
    int low = 0;
    int high = values.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (values[mid] == target) {
            return mid;
        } else if (values[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

Extra practice: searching the same list for 42 takes three steps: (low 0, high 4, mid 2) → (3, 4, 3) → (4, 4, 4), found at index 4.

Common mistakes that cost marks

  • Running a binary search on unsorted data.
  • Using / instead of // in Python for the midpoint. Python's / gives a decimal, which can't be used as an index.
  • Leaving out the base case in recursion, which recurses forever.
  • Stating Big O without a reason, for example "O(n²) because there's a loop inside a loop over n items".

Frequently asked questions

Which sorting algorithms are on the syllabus?
Bubble sort and selection sort. At HL, quicksort appears as an example of recursion.

Can I use built-in sort or search functions?
Exam questions often ask you to write the algorithm yourself, so practise writing them from scratch.

Go further