- Understand the six most common complexity classes and their growth patterns
- Recognize when each complexity class appears in real algorithms
- Learn when to accept O(n²) and when to avoid O(2ⁿ)
- Balance time and space complexity trade-offs
Common Time Complexities
You've learned the notation. Now let's see what these complexity classes actually mean in practice. Each one has a different growth pattern, and knowing them helps you pick the right approach for your problem.
O(1) - Constant Time
Doesn't matter how big the input gets, the time stays the same. Accessing an array element by index (arr[5]) takes the same time whether the array has 10 items or 10 million. Same with pushing/popping from a stack, or checking if a number is even with n % 2 == 0.
Think of it like looking up a word in a dictionary when someone gives you the exact page number. You just flip directly there.
O(log n) - Logarithmic Time
This is the "cut the problem in half each time" complexity. Binary search is the classic example: you look at the middle element, then eliminate half the remaining options, then half again. Finding an element in a balanced binary search tree works the same way.
Finding a name in a phone book by repeatedly dividing the search space — you don't check every page, you halve your way to the answer.
O(n) - Linear Time
Time grows proportionally with input size. Double the input, double the time. Finding the maximum in an unsorted array means checking each element once. Linear search, printing all elements, any single pass through data — all O(n).
Like counting people in a line by checking each person once. 100 people takes roughly 10 times longer than 10 people.
O(n log n) - Linearithmic Time
A bit more than linear, but still quite good. This is what you get with efficient sorting algorithms like merge sort, quick sort (average case), and heap sort. Some graph algorithms land here too.
Sorting a deck of cards using an efficient method — you're doing more than just looking at each card once, but you're not comparing every card to every other card either.
O(n²) - Quadratic Time
Nested operations over the data. Simple sorting algorithms like bubble sort, insertion sort, and selection sort fall here. Checking all pairs in a collection — like comparing every person in a room to every other person — that's quadratic.
If everyone at a party needs to shake hands with everyone else, that's n² handshakes. Small parties work fine, but this gets ugly fast with larger groups.
O(2ⁿ) - Exponential Time
Doubles with each additional element. Solving the traveling salesman problem with brute force, generating all subsets of a set, recursive algorithms without memoization — these can all hit exponential time.
Trying every possible combination of a lock. Even for small inputs, this gets out of hand fast. A lock with 10 positions? That's 1,024 combinations. With 20? Over a million.
Complexity Comparison
| Complexity | n=10 | n=100 | n=1000 | Acceptable for... |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | Any size |
| O(log n) | 3 | 7 | 10 | Large datasets |
| O(n) | 10 | 100 | 1000 | Large datasets |
| O(n log n) | 30 | 700 | 10000 | Medium-large datasets |
| O(n²) | 100 | 10000 | 1000000 | Small datasets only |
| O(2ⁿ) | 1024 | 10³⁰ | 10³⁰⁰ | Tiny datasets only |
Picking the right complexity for your situation
Use O(1) when you need guaranteed fast performance regardless of data size. Hash maps, array indexing, stack operations — these are your friends.
O(log n) works when your data has structure. Sorted arrays enable binary search. Balanced trees give you logarithmic lookups.
O(n) is unavoidable when you need to examine every element. Finding a max, filtering, mapping — you can't skip items.
O(n log n) is the sweet spot for sorting. Merge sort, quicksort (average case), heap sort — these are the workhorses of efficient sorting.
O(n²) is sometimes acceptable for small, fixed-size inputs. Insertion sort actually beats quicksort for tiny arrays (say n < 10) because of lower overhead.
Avoid O(2ⁿ) whenever possible. If you're hitting exponential time, there's usually a better approach using dynamic programming or greedy algorithms.
Don't forget about space
Time isn't the only cost. Some algorithms trade memory for speed:
- O(1) space means in-place — you modify the original data without creating new collections
- O(n) space means creating new collections proportional to input size
- O(n²) space shows up in 2D matrices, adjacency matrices for graphs
Know your constraints. What input sizes will you handle? Balance time and space — sometimes faster algorithms use more memory. Big O typically describes worst case, but constants matter for small n. An O(n²) algorithm might actually be faster than O(n) when n is 10 because of lower overhead.