Definition
Big O notation describes the upper bound (worst-case) growth rate of an algorithm's time or space complexity as the input size increases. It provides a standardised way to compare algorithm efficiency.
Common Big O Complexities
Key Point
| Big O | Name | Typical example | Growth intuition |
|---|---|---|---|
| O(1) | Constant | Array lookup by index | Cost stays about the same as n grows |
| O(log n) | Logarithmic | Binary search | Doubling n adds only a small extra cost |
| O(n) | Linear | Linear search | Cost grows in direct proportion to n |
| O(n log n) | Log-linear | Merge sort, quicksort (average) | Efficient for large sorting tasks |
| O(n²) | Quadratic | Bubble sort, insertion sort (worst/avg) | Cost grows rapidly as n increases |
| O(2ⁿ) | Exponential | Brute-force recursion | Explodes quickly; impractical at scale |
Time vs Space Complexity
Key Point
| Complexity type | What it measures | Typical trade-off |
|---|---|---|
| Time complexity | How runtime grows with input size n | Faster runtime may need extra memory |
| Space complexity | How extra memory use grows with n | Lower memory usage may increase runtime |
Working Out the Complexity of an Algorithm
Definition
The complexity of an algorithm is found by working out how the number of steps it takes, or the memory it needs, grows as the number of items, n, increases. Constants and smaller terms are ignored, so only the fastest-growing term is kept: an algorithm that takes 3n + 5 steps is O(n).
| What the algorithm does | Complexity | Reason |
|---|---|---|
| A fixed number of steps with no loop over the data | O(1), constant | The number of steps does not depend on n |
| Halves the data still to be dealt with on each pass | O(log n), logarithmic | Doubling n adds only one more pass |
| One loop that visits each item once | O(n), linear | n items need n passes |
| One loop over the data nested inside another | O(n²), polynomial | The inner loop makes n passes for each of the n passes of the outer loop |
| Tries every combination, so each extra item doubles the work | O(2ⁿ), exponential | The number of steps doubles for every item added |
Worked Example
Finding the Big O of a Nested Loop
The inner loop runs n times for each of the n passes of the outer loop, so the comparison is made n × n times. The time complexity is O(n²), which is polynomial. The algorithm needs only the two counters however large n is, so its space complexity is O(1).
pseudocode
for i = 0 to n - 1:
for j = 0 to n - 1:
if i != j AND items[i] == items[j] then
print("Duplicate found")
end if
end for
end for
Key Point
Polynomial complexity means n raised to a fixed power, such as O(n²) or O(n³). O(n²) is also called quadratic.
Best, average and worst case can differ for the same algorithm. A linear search is O(1) in the best case, when the target is the first item, and O(n) in the worst case, when the target is last or not in the list.
Best, average and worst case can differ for the same algorithm. A linear search is O(1) in the best case, when the target is the first item, and O(n) in the worst case, when the target is last or not in the list.