Big O describes how the work an algorithm does grows as the input size n grows. It is not a time in seconds.
Two rules turn an exact step count into Big O:
- Drop constants:
3nbecomesO(n). - Keep only the fastest-growing term:
n² + 5n + 100becomesO(n²).
| Big O | Name | Example |
|---|---|---|
| O(1) | constant | a[i], HashMap get |
| O(log n) | logarithmic | binary search |
| O(n) | linear | one loop over the array |
| O(n log n) | linearithmic | merge sort |
| O(n²) | quadratic | two nested loops |
| O(2ⁿ) | exponential | naive recursive Fibonacci |
int count = 0;
for (int i = 1; i < n; i *= 2) count++; // i doubles: about log2(n) stepsThe trap: constants still matter for small inputs. An algorithm doing 100n steps is slower than one doing n² steps until n passes 100. Big O only tells you who wins eventually.
In interviews: always state both time and space complexity of your solution without being asked, and say which term dominates.