Programming Algorithms (IB CS B2.4): Big O, Searching, Sorting and Recursion

Two programs can solve the same problem, yet one finishes instantly while the other crawls. B2.4 is about understanding why. You will learn to measure an algorithm's efficiency with Big O notation, to search and sort data, and (at HL) to write algorithms that call themselves. These are exam favourites and they reward practice, so let's work through them.

What is Big O notation?

Big O notation describes how the amount of work an algorithm does grows as the input gets bigger. It is not a stopwatch; it ignores the exact machine and focuses on the shape of the growth, which is what matters when data scales up.

The everyday intuition is "what happens if I double the data?" If the work stays the same, that is O(1), constant time, like looking up an item in an array by its index. If the work roughly doubles, that is O(n), linear time, like checking every item once. If the work only creeps up slowly, that is O(log n), logarithmic time, which is what you get when each step halves the problem. And if the work quadruples when you double the data, that is O(n²), quadratic time, which gets slow fast.

The golden rule for the exam: flatter curves are better. You want the smallest growth your problem allows.

How do linear search and binary search work?

A linear search is the simple approach: start at the first item and check each one in turn until you find your target or run out of items. It works on data in any order, which is its strength, but it can be slow, because in the worst case you check every element. That makes it O(n).

A binary search is much faster, but it has one firm requirement: the data must be sorted. It looks at the middle item, compares it to the target, and throws away the half that cannot possibly contain it. Then it repeats on the half that remains. Because each step halves the search space, it is O(log n), which is dramatically quicker for large lists.

How do bubble sort and selection sort work?

Sorting puts data into order, often so a binary search becomes possible. B2.4 asks for two simple sorts, and both are O(n²).

A bubble sort repeatedly walks through the list comparing each pair of neighbours and swapping them if they are in the wrong order. After one full pass, the largest value has "bubbled" to the end. You repeat the passes, each one placing the next-largest value, until no swaps are needed.

A selection sort works differently. On each pass it scans the unsorted part of the list to find the largest remaining value, then moves that value to its final position. It does fewer swaps than bubble sort, but it still has to scan the unsorted part every pass, so its time complexity is the same.

What is recursion? (HL)

Recursion (HL only) is when a function solves a problem by calling itself on a smaller version of the same problem. It keeps doing this until it hits a base case, a version simple enough to answer directly without recursing further. Then the partial answers unwind back up to give the final result.

Every recursive function needs two things. The base case stops the recursion, and the recursive case moves towards that base case by calling itself with a smaller input. Miss the base case, or fail to shrink the input, and the function calls itself forever, which causes an infinite recursion and eventually a stack overflow.

A worked example: binary search by hand

Let's trace a binary search for the value 7 in this sorted list, with indices shown:

Set low = 0 and high = 5. The middle index is (0 + 5) / 2 = 2 (rounded down), so we look at value 4. Our target 7 is bigger than 4, so it must be in the right half. We move low = 3.

Now low = 3, high = 5, so the middle is (3 + 5) / 2 = 4, which holds value 7. That is our target, found in just two comparisons. A linear search would have taken five. Trace it slowly and you can see why halving beats checking one by one: each step throws away half of what is left.

Common exam mistakes

A common slip is using binary search on unsorted data. Binary search only works if the list is sorted first; on unsorted data it gives wrong answers. If the data is not sorted, you either sort it first or use a linear search.

Students also quote Big O loosely. Bubble sort and selection sort are O(n²), linear search is O(n), and binary search is O(log n). Learn these pairings, because questions often ask you to state and justify the complexity.

At HL, the biggest recursion error is forgetting the base case, or writing one the function never reaches. Always check that every recursive call moves closer to the base case, and that the base case actually stops the chain.

Finally, when tracing, watch your off-by-one and your rounding. Getting the middle index wrong, or losing track of low and high, is the easiest way to drop marks on an otherwise correct trace.

Quick recap

Big O describes how an algorithm's work grows with input size; flatter growth is better. Linear search checks each item in turn, O(n); binary search halves a sorted list each step, O(log n). Bubble sort swaps adjacent pairs; selection sort places the largest each pass; both are O(n²). Recursion (HL) solves a problem by calling itself on a smaller input until it reaches a base case. Every recursion needs a base case and a step that shrinks the input, or it never stops.

Frequently asked questions

What is Big O notation used for? Big O notation describes how the number of operations an algorithm performs grows as the input size grows. It lets you compare algorithms by their scalability, independent of the specific computer, so you can choose the most efficient approach for large data.

What is the difference between linear search and binary search? A linear search checks each item in turn and works on data in any order, with time complexity O(n). A binary search repeatedly halves a sorted list, with time complexity O(log n), so it is much faster, but it only works if the data is already sorted.

Why must data be sorted for a binary search? Binary search assumes that if the middle value is smaller than the target, the target must be to the right, and vice versa. This is only true when the data is in order. On unsorted data that assumption breaks, so the search can discard the wrong half and miss the target.

What is the time complexity of bubble sort and selection sort? Both bubble sort and selection sort have a time complexity of O(n²), because each repeatedly works through the list a number of times proportional to its length. They are simple to understand but inefficient for large data sets compared with sorts like merge sort or quicksort.

What is recursion in programming? Recursion is when a function calls itself on a smaller version of a problem until it reaches a base case it can answer directly. The results then unwind back up to produce the final answer. The factorial and Fibonacci calculations are classic recursive examples. This is HL content.

What is a base case in recursion? A base case is the condition under which a recursive function stops calling itself and returns a value directly. Without a reachable base case, the function would call itself forever, causing an infinite recursion and eventually a stack overflow. This is HL content.

 Looking for a printable summary? Grab the Programming Algorithms (IB CS B2.4): Big O, Searching, Sorting and Recursion, a three-page knowledge organiser covering everything above.

Looking for an IB Computer Science tutor?

Hi, I'm Yuness, the tutor behind Shuttle Learning. I work one to one with IB Computer Science students at SL and HL, and I deliberately take on only a handful each year so every student gets my full attention. Most go on to earn the 6s and 7s they were aiming for, in the final exams and the IA alike.

If you would like that kind of support, book a free 15-minute call and tell me what you are stuck on. You can press BOOK A LESSON .