Big-O, Big-Omega, Big-Theta
CS205 Data Structures
Use arrow keys to navigate | Interactive slides ahead!
The same problem can be solved in vastly different amounts of time depending on the algorithm.
Searching for a name in a phone book:
Sorting 1 million exam papers: a bad algorithm takes years, a good one finishes in seconds.
At n = 1,000 on a 1 GHz machine. Each bar = relative operation count (log scale).
Algorithm analysis lets us predict performance before we run the code, and compare algorithms independently of hardware.
An algorithm is a step-by-step procedure for solving a problem in a finite number of steps.
Pseudocode is language-independent — the analysis works for any implementation.
We analyze the algorithm, not the program. The algorithm is the idea; the program is one implementation.
"My laptop ran it in 2 seconds" tells us almost nothing about the algorithm itself.
Instead of timing, we count primitive operations as a function of input size n.
Each primitive operation takes constant time — O(1).
Step through findMax and watch the operation counter. Click ▶ to advance.
Best case: 3n ops. Worst case: 5n − 2 ops. Both are O(n) — the constants don't matter!
Drag the slider to see how functions diverge as n grows. This is why Big-O matters!
Driving 1000 miles? Starting 5 feet ahead doesn't matter. The dominant term determines everything at scale.
f(n) is O(g(n)) if there exist positive constants c and n₀ such that:
f(n) ≤ c · g(n) for all n ≥ n₀
Big-O is like "this trip takes at most 3 hours." Might be less, never more.
∴ 3n + 5 is O(n) with c=4, n₀=5.
∴ n² + 3n is O(n²) with c=2, n₀=3.
c and n₀ are not unique — many valid pairs exist. Also, 3n+5 is technically O(n²) too, but that's a loose (less useful) bound.
f(n) is Ω(g(n)) if there exist positive constants c and n₀ such that:
f(n) ≥ c · g(n) for all n ≥ n₀
3n + 5 is Ω(n): choose c=3, n₀=1. 3n+5 ≥ 3n ✓
Ω is like "this trip takes at least 1 hour." Might take more, never less.
f(n) is Θ(g(n)) if there exist positive constants c₁, c₂, and n₀ such that:
c₁·g(n) ≤ f(n) ≤ c₂·g(n)
for all n ≥ n₀
f(n) is Θ(g(n)) iff f(n) is both O(g(n)) and Ω(g(n)).
3n + 5 is Θ(n):
Θ gives the exact growth rate. When someone says "this is n log n," they really mean Θ(n log n).
From fastest to slowest (best to worst for runtime):
| Name | Big-O | n = 10 | n = 100 | n = 1,000 | Example |
|---|---|---|---|---|---|
| Constant | O(1) | 1 | 1 | 1 | Array index |
| Logarithmic | O(log n) | 3 | 7 | 10 | Binary search |
| Linear | O(n) | 10 | 100 | 1,000 | Linear search |
| Linearithmic | O(n log n) | 30 | 700 | 10,000 | Merge sort |
| Quadratic | O(n²) | 100 | 10,000 | 1,000,000 | Bubble sort |
| Cubic | O(n³) | 1,000 | 10⁶ | 10⁹ | Matrix multiply |
| Exponential | O(2ⁿ) | 1,024 | ~10³⁰ | ~10³⁰¹ | Subsets |
| Factorial | O(n!) | 3,628,800 | ~10¹⁵⁸ | LOL | Permutations |
Anything beyond O(n²) becomes impractical quickly. O(2ⁿ) and O(n!) are unsolvable for n > 30–50.
Multiply for nested loops. Halving/doubling = logarithmic. O(n) body inside O(n) loop = O(n²).
Recursive algorithms use recurrence relations.
Write the recurrence → expand → find the pattern → determine total. log(n) levels × n cost per level = O(n log n).
| Case | When? | Comparisons |
|---|---|---|
| Best | Target is first | 1 = O(1) |
| Worst | Target last / absent | n = O(n) |
| Average | Equally likely anywhere | n/2 = O(n) |
We usually analyze worst case — it gives a guarantee on performance.
Don't confuse Big-O (bound type) with worst case (input type). You can say "the best case is O(1)."
Sometimes a single operation is expensive, but averaged over many operations it's cheap.
When full, double capacity and copy everything.
Individual insert can be O(n). But amortized cost per insert is O(1). Expensive operations are rare enough to average out.
Like saving a little each day, paying rent monthly. Average daily cost is still constant.
Not just time — memory usage matters too.
Use only O(1) extra space.
| Algorithm | Time | Space (aux) |
|---|---|---|
| Linear search | O(n) | O(1) |
| Binary search (iterative) | O(log n) | O(1) |
| Binary search (recursive) | O(log n) | O(log n)* |
| Merge sort | O(n log n) | O(n) |
| Insertion sort | O(n²) | O(1) |
* Recursive calls use stack space
Recursion uses stack space! Depth n = O(n) space even with no arrays.
| Algorithm | Best | Average | Worst |
|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) |
| Insertion Sort | O(n) | O(n²) | O(n²) |
| Selection Sort | O(n²) | O(n²) | O(n²) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) |
Comparison-based sorting has a proven lower bound of Ω(n log n).
| Algorithm | Time | Requires |
|---|---|---|
| Linear Search | O(n) | Nothing |
| Binary Search | O(log n) | Sorted array |
| Hash Lookup | O(1) avg | Hash table |
| Algorithm | Time |
|---|---|
| BFS / DFS | O(V + E) |
| Dijkstra's | O((V+E) log V) |
"Linear search is O(n²)" is technically true but misleading. The tight bound is Θ(n). Always give the tightest bound.
1,000,000·n vs n² — for n < 1,000,000 the "slower" n² is actually faster!
log₂(n) = log₁₀(n) × 3.32... The 3.32 is a constant → dropped in Big-O.
So O(log₂ n) = O(log₁₀ n) = O(ln n)
Best/worst/average case = which input.
O / Ω / Θ = type of bound on the function.
These are separate concepts!
Single loop? → O(n) | Nested? → O(n²)
Halving? → O(log n) | Divide & conquer? → O(n log n)
| Notation | Meaning | Bound |
|---|---|---|
| O(g(n)) | f(n) ≤ c·g(n) | Upper |
| Ω(g(n)) | f(n) ≥ c·g(n) | Lower |
| Θ(g(n)) | c₁·g(n) ≤ f(n) ≤ c₂·g(n) | Tight |
A good algorithm on slow hardware will always beat a bad algorithm on fast hardware — you just need large enough input.
Determine the time complexity of each code snippet.
Click the complexities in order from fastest growing (best) to slowest growing (worst).
5 tricky questions about algorithm analysis. How many can you get?
Enter custom values of n and see how many operations each complexity class requires.
n = 10 → everything is fast. n = 1,000 → n² starts to hurt. n = 1,000,000 → only O(n log n) and below are practical!