What is Big-O notation?
Big-O describes how an algorithm's cost scales with input size, ignoring constants. O(n) means doubling the input roughly doubles the work; O(n²) means it quadruples.
| Notation | Name | Doubling n means |
|---|---|---|
| O(1) | Constant | No change |
| O(log n) | Logarithmic | One more step |
| O(n) | Linear | Twice the work |
| O(n log n) | Linearithmic | Slightly more than double |
| O(n²) | Quadratic | Four times the work |
| O(2ⁿ) | Exponential | Squares the work — unusable fast |
#What each looks like in code
items[0] # O(1) — direct index
for x in items: ... # O(n) — one pass
for a in items:
for b in items: ... # O(n²) — nested passes
items.sort() # O(n log n)
x in some_set # O(1) — hash lookup
x in some_list # O(n) — linear scanThat last pair is the one that matters most in practice. Turning a list membership test into a set lookup is the single most common real optimisation.
#Constants are dropped
O(2n + 50) is written O(n). Big-O describes the shape of the growth, not the exact runtime. On small inputs an O(n²) algorithm with a tiny constant can beat an O(n log n) one — which is why real sort implementations switch to insertion sort for short subarrays.
#Space complexity too
The same notation describes memory. A recursive function that stacks n frames is O(n) space; an iterative one that reuses variables is O(1).
#Why interviews ask
Not to make you recite a table. They want to see whether you notice that your nested loop over 10,000 items is 100 million operations, and whether you know that a hash map fixes it. State the complexity of your solution before they ask.