Programs constantly need to find data and put data in order. This unit covers the two search algorithms and two sort algorithms you need for IB Computer Science (B2.4.2 and B2.4.3), and how we measure their efficiency with Big O notation (B2.4.1). Knowing which algorithm to use, and why, is a common exam topic.
Slide 1 / 4
Big O efficiency
Big O notation measures the efficiency of an algorithm by describing how the number of operations grows as the input size (n) gets bigger. It describes the worst case, the upper bound on the work needed.
Common orders from best to worst include O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) log linear, and O(n^2) quadratic.
O(log n) happens when the data is halved each step (like a binary search). O(n) means the work grows in direct proportion to n (a single loop). O(n^2) comes from a loop inside a loop (like bubble and selection sort).
Big O lets you compare algorithms and predict how well they scale, so you can choose the right one for large data sets.
Check you've got it
0/4
1. Which statement about a linear search is correct?
2. Before you can use a binary search on a list, what must be true of the data?
3. A bubble sort (sorting lowest to highest) is run on the array [5, 3, 8, 1]. What does the array look like after one complete pass?
4. A binary search looks for the value 23 in the sorted array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indexes 0 to 9), always checking the middle item and rounding the middle index down. How many items does it compare against 23 before it finds it?
Free revision content. Multiple-choice answers are marked instantly. Written answers are marked by AI on /free-mark.