Algorithms & Complexity
IB Syllabus: B2.4: Algorithms and complexity
Overview
Any program can produce the correct answer, but two correct programs are not necessarily equal. One may be dramatically faster on large inputs. This section covers the classic algorithms every CS student should know, along with the tools to measure and compare them.
| Topic | Algorithm Type | Complexity | Syllabus |
|---|---|---|---|
| Searching Algorithms | Search | O(n) / O(log n) | B2.4.2 |
| Sorting Algorithms | Sort | O(n²) | B2.4.3 |
| Big-O Notation | Analysis | - | B2.4.1 |
| Recursion | HL Only | Varies | B2.4.4, B2.4.5 |
| Quicksort | HL Only | O(n log n) avg | B2.4.4 |
The Big Question
How do we measure and compare algorithms? The key insight: as input size grows, some algorithms slow down gracefully while others grind to a halt.
| If input doubles… | O(1) | O(log n) | O(n) | O(n²) |
|---|---|---|---|---|
| Time change | None | +1 step | Doubles | Quadruples |
Big O notation will be covered in detail after sorting algorithms. For now, understand that O(n) means “visits every element” and O(log n) means “halves the work each step”.
Teaching Sequence
Algorithms are taught in step 3 of the programming sequence, after 1D arrays and before methods:
- Searching algorithms (linear search, binary search)
- Sorting algorithms (bubble sort, selection sort)
- Big O notation (formalised after seeing concrete examples)
- Recursion and quicksort (HL only, after methods)