InternshipBig O: measuring speed
How to say how an algorithm grows as its input grows.
Big O describes how the work grows as input grows. It ignores small details and focuses on the shape of the growth, so you can compare approaches before writing them.
| Big O | Name and example |
|---|---|
O(1) | Constant: read a list item by index |
O(log n) | Logarithmic: binary search |
O(n) | Linear: scan a list once |
O(n log n) | Good sorting algorithms |
O(n²) | Quadratic: a loop inside a loop |
O(2ⁿ) | Exponential: trying every subset |
Coding tests often allow about 100 million simple steps per second. With n = 100,000, O(n²) is far too slow, while O(n log n) is fine.
Same problem, faster approach
Does a list contain a duplicate? Comparing every pair is O(n²). Remembering what you have seen in a set is O(n).
Expected output
True False