Big O Notation and Algorithm Efficiency
Describe the efficiency of specific algorithms by calculating their Big O notation to analyse their scalability
In this lesson
- Explaining time and space complexity
- Calculating the Big O notation of an algorithm from its loops
- Comparing how the common complexity classes scale as the input grows
- Choosing an algorithm based on scalability and efficiency requirements
LearnMeasuring efficiency
LearnCommon complexity classes
From the most to the least efficient.
| Big O | Name | Typical example |
|---|---|---|
| O(1) | Constant | Accessing an array element by its index; push and pop on a stack. |
| O(log n) | Logarithmic | Binary search: the data still to be searched halves at every step. |
| O(n) | Linear | Linear search; any single loop that visits every item once. |
| O(n log n) | Linearithmic | Efficient sorts such as merge sort, and quicksort in the average case. |
| O(n²) | Quadratic | Bubble sort and selection sort; two nested loops that each run up to n times. |
| O(2ⁿ) | Exponential | Trying every subset of n items; the naive recursive Fibonacci function. |
| O(n!) | Factorial | Trying every possible order of n items, e.g. every route through n towns. |
LabHow the classes grow
Move the slider to change n and watch how many operations each class needs.
| Big O | Operations for this n | Time at 10⁹ operations per second | |
|---|---|---|---|
| O(1) constant | 1 | 1 ns | |
| O(log n) logarithmic | 5 | 5 ns | |
| O(n) linear | 16 | 16 ns | |
| O(n log n) linearithmic | 80 | 80 ns | |
| O(n²) quadratic | 256 | 256 ns | |
| O(2ⁿ) exponential | 65,536 | 65.5 µs | |
| O(n!) factorial | 2.09 × 10¹³ | 5.81 hours |
The bars use a logarithmic scale: the bar grows by the same length each time the number of operations is multiplied by ten. The O(log n) row shows the most comparisons a binary search of n items needs.
LearnCalculating Big O from code
CodeO(1): no loop
75.0
A division and a multiplication, whatever the values: the work never changes.
CodeO(n): one loop
23
The loop compares each remaining element once, so the number of comparisons is n − 1: it grows in line with n.
CodeO(n²): nested loops
True
In the worst case (no duplicates) the inner loop runs n times for each of the n passes of the outer loop: n × n comparisons.
CodeO(log n): halving
9
Halving 1000 repeatedly reaches 1 after 9 steps (whole-number division). Doubling n to 2000 would add only one more step.
CheckWhich class?
Classify the worst-case time complexity of each task for n items.
- Read the first item of an array
- Add up every number in a list
- Compare every student’s mark with every other student’s mark
- Guess a number from 1 to n, always guessing the middle of the numbers still possible and being told “higher” or “lower”
- Print a grid of n rows and n columns
- Pop the top item off a stack
- Find the cheapest price in an unsorted list
- Find a word in a sorted dictionary by opening it at the middle of the remaining pages each time
LearnSpace complexity
CheckQuick check
A linear (O(n)) search takes 3 ms on a list of 5,000 items. Roughly how long would it take on 20,000 items?
LearnChoosing an algorithm
ExamWorked exam answer
Determine the Big O time complexity of weeklyReport, where n is the number of values in sales. Justify your answer.
ReviewMistakes examiners see
Saying that nested loops are always O(n²): check how many times each loop runs.
Giving the best case: Big O describes the worst case unless the question says otherwise.
Keeping constants, e.g. writing O(2n) or O(n² + n), instead of O(n) and O(n²).
In a Describe or Explain answer about efficiency, say what n is and how the number of operations changes when n grows.
Exam practiceExam-style questions
4 questions · 11 marks. Answer each one first, then mark it yourself against the markscheme. Your answers are saved in this browser only.
A music app stores the titles of the songs in a user’s library in an array. Each song also has a tempo in beats per minute (bpm).
State the Big O time complexity of songAt and of countLonger, and the extra space complexity of countLonger, where n is the number of songs.
similarPairs counts the pairs of songs whose tempos differ by 2 bpm or less, so that the app can suggest songs to play one after the other. Explain why its time complexity is O(n²), even though the inner loop does not always run n times.
For a library of 2,000 songs, similarPairs takes 0.5 seconds. Calculate roughly how long it would take for 10,000 songs.
To sort songs by tempo, the developer can use an O(n²) sort or an O(n log n) sort. Explain why the choice hardly matters for a playlist of 20 songs, but does matter for a streaming service’s catalogue of 2 million songs.
0 of 4 questions marked. Mark every question to see your total.
Exam-style questions written for Praxis IB in the format of the 2027 specimen papers. They are not IB past-paper questions.