Big O notation describes how an algorithm's running time (or memory) grows as its input grows, ignoring constant factors. O(1) means constant time, O(log n) logarithmic, O(n) linear, O(n log n) the cost of good sorting, and O(n²) quadratic, which becomes painfully slow on large inputs. It lets you compare approaches before you write or run them.
Why do we need Big O?
Timing code with a stopwatch depends on the computer, the language and the data. Big O asks a more useful question: if the input doubles, what happens to the work? If the work doubles, the algorithm is linear. If it quadruples, it is quadratic. That answer stays true on any machine, which is why interviewers, database designers and ML engineers all use it.
What do the common complexity classes mean?
| Big O | Name | Example |
|---|---|---|
| O(1) | Constant | Reading arr[5]; looking up a key in a hash map (average) |
| O(log n) | Logarithmic | Binary search in a sorted array; balanced-tree lookups |
| O(n) | Linear | Finding the maximum of an unsorted list |
| O(n log n) | Linearithmic | Merge sort, heap sort, Python's sorted() |
| O(n²) | Quadratic | Comparing every pair; bubble sort |
| O(2ⁿ) | Exponential | Trying every subset; naive recursive Fibonacci |
How big is the difference in practice?
Here is the number of basic steps each class needs for an input of one million items (n = 1,000,000), using log₂:
| Complexity | Steps for n = 1,000,000 | At 100 million steps per second |
|---|---|---|
| O(1) | 1 | Instant |
| O(log n) | ≈ 20 | Instant |
| O(n) | 1,000,000 | ≈ 0.01 seconds |
| O(n log n) | ≈ 20,000,000 | ≈ 0.2 seconds |
| O(n²) | 1,000,000,000,000 | ≈ 2.8 hours |
Pure arithmetic. Even at n = 1,000, quadratic needs 100× the work of n log n, so the first three bars barely register.
How do you work out Big O from code?
Count how many times the most frequent operation runs, as a function of n, then keep only the fastest-growing term and drop constants.
- A single loop over n items → O(n).
- A loop inside a loop, each over n → O(n²).
- Halving the problem each step (binary search) → O(log n).
- Two separate loops one after the other → O(n) + O(n) = O(n).
- Splitting in half and doing linear work at each level (merge sort) → O(n log n).
Example: checking whether a list has duplicates by comparing every pair is O(n²). Putting items into a set and checking membership is O(n) on average, because set lookups are O(1). Same result, wildly different cost on big data: that single change is the kind of thing interviews test.
What are best, average and worst case?
Many algorithms behave differently depending on the data. Quick sort is O(n log n) on average but O(n²) in its worst case (for example, already sorted data with a naive pivot). Hash-map lookups are O(1) on average but O(n) in the rare worst case. When people say "Big O" without qualification they usually mean the worst case, but always check which one a statement refers to.
What about space complexity?
Space complexity measures extra memory. Merge sort needs O(n) extra space for merging; heap sort sorts in place with O(1) extra space. Recursion uses stack space proportional to its depth. In data and AI work, memory often runs out before time does, so space complexity matters as much as speed.
Where does Big O matter beyond interviews?
- Databases: an index turns an O(n) table scan into an O(log n) lookup. See database indexing explained.
- Data processing: a nested loop over two large tables can take hours; a hash join takes seconds.
- Machine learning: k-nearest neighbours searching every point is O(n) per prediction; vector indexes make similarity search fast.
- LLMs: standard attention is O(n²) in sequence length, which is exactly why long context windows are expensive. See the attention mechanism explained.
What are some worked examples?
Let's analyse three short functions in words.
Example 1: sum of a list. You visit each of the n items once and add it to a running total. One pass, constant work per item: O(n) time, and O(1) extra space because you store only the total.
Example 2: does any pair add up to a target? The obvious approach checks every pair with two nested loops: about n²/2 comparisons, so O(n²). A better approach walks through the list once, and for each number checks whether target − number is already in a set of numbers seen so far. Set lookups are O(1) on average, so the whole thing is O(n) time with O(n) extra space for the set. This trade (more memory for much less time) is one of the most common patterns in algorithm design.
Example 3: binary search. In a sorted list, compare the target with the middle element, then discard the half that can't contain it. Each step halves the remaining items: 1,000,000 → 500,000 → 250,000 … → 1 takes about 20 steps. That's O(log n), and it only works because the data is sorted, which is why sorting (O(n log n)) is so often worth paying for once.
What are the common mistakes when calculating Big O?
- Forgetting hidden loops.
if x in my_listis a linear search, O(n). Inside another loop it quietly makes your code O(n²). Using a set instead makes it O(1). - Treating string concatenation as free. Building a long string by repeated
+=in some languages copies the string each time; joining a list of parts is linear. - Mixing up variables. Two different inputs of sizes n and m give O(n × m), not O(n²).
- Over-focusing on constants. O(2n) is O(n). Constants matter for real speed, but they don't change the growth class.
- Ignoring the data. Average and worst cases can differ a lot; know which one your input is likely to trigger.
Which data structure operations should you memorise?
| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array / Python list | O(1) | O(n) | O(n) (O(1) at end) | O(n) |
| Linked list | O(n) | O(n) | O(1) at a known node | O(1) at a known node |
| Hash map / set (average) | — | O(1) | O(1) | O(1) |
| Balanced binary search tree | O(log n) | O(log n) | O(log n) | O(log n) |
| Binary heap | O(1) min/max | O(n) | O(log n) | O(log n) min/max |
Knowing this table by heart lets you answer most "which structure should I use?" questions in seconds, in interviews and in real design discussions.
How is Big O asked in interviews?
Interviewers rarely ask for definitions. They give you a problem, let you write a solution, then ask "what's the time and space complexity, and can you do better?" A strong answer states the complexity of your first approach honestly, identifies the bottleneck (usually a nested loop or repeated search), and proposes a structure that removes it: a hash map for lookups, sorting plus two pointers, a heap for "top k", or binary search on sorted data. Practising that conversation out loud, not just writing code, is what turns Big O knowledge into interview performance.
How should you practise?
For every problem you solve, write down its time and space complexity before running it, then look for a faster approach. Next, learn the standard algorithms in sorting algorithms explained and follow a DSA preparation plan. Program Zero spends ten weeks on data structures and algorithms; the DSA course page lists every topic.