Big O notation describes how an algorithm’s time or memory requirement grows as its input size, usually represented by , increases. To calculate it, count how often the algorithm’s dominant operation executes, express this as a function of , and retain only the fastest-growing term.
How Big O Works
Big O gives an asymptotic upper bound on growth. It focuses on scalability rather than an exact execution time, because actual time also depends on hardware, programming language, and implementation.
Use this method:
- Define the input size , such as the number of elements in an array.
- Identify the operation repeated most often.
- Count its executions in terms of .
- Remove constant factors and lower-order terms.
For example, if the operation count is , the term dominates for large inputs. Therefore, the complexity is , not .
| Algorithm pattern | Approximate operation count | Big O complexity |
|---|---|---|
| One statement | ||
| One loop through all data | ||
| Two nested loops of size |
For two nested loops, each running times, the inner operation executes times. By contrast, two consecutive loops each execute times, producing , which simplifies to .
When analysing conditional branches, first determine whether the question asks for best-case, average-case, or worst-case behaviour. For the worst case, follow the branch that performs the most operations. If separate stages have complexities and , add them and retain .
A common misconception is that Big O always means worst-case complexity. Big O is formally an upper bound; however, exam questions often ask students to use it when analysing an algorithm’s worst-case time complexity.
IB Exam Technique
For B2.4 Programming algorithms, state the input size, identify the repeated operation, show the count, and then simplify. Do not merely give : justify it by linking loop structure or input reduction to the growth rate.
