Think together · Start with a little story
The robot labels three kinds of work: look at the first card, look at every card, or compare every pair.
Lay out the process
- O(1)The count does not grow with n
- O(n)Grows linearly with n
- O(n²)May grow with the square of n
Big O is commonly used to describe an upper bound on growth and compare an algorithm’s main workload.
O(1) does not mean only one operation; doing ten fixed operations still does not grow with n. O(n) does not guarantee exactly n operations.
01What does O(1) mean?
int x = a[5];As long as the index is valid, the basic work for accessing an ordinary array by index does not increase when the array gets longer. We often write this as O(1).
02What does O(n) mean?
for (int i = 0; i < n; i++) {
sum += a[i];
}If n doubles, the loop’s work roughly doubles too. This is linear growth, or O(n).
03What does O(n²) mean?
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
work();
}
}Both loops run n times, so the total work is about n × n, or O(n²).
04How different are their growth rates?
| n | O(1) | O(n) | O(n²) |
|---|---|---|---|
| 10 | Constant scale | 10 | 100 |
| 1,000 | Constant scale | 1,000 | 1,000,000 |
| 100,000 | Constant scale | 100,000 | 10,000,000,000 |
05Are two nested loops always O(n²)?
No.
for (int i = 0; i < n; i++) {
for (int j = 0; j < 10; j++) {
work();
}
}The inner loop always runs 10 times, so the total work is 10n, which is still O(n) asymptotically.
06Is O(1) always faster than O(n)?
When n is large enough, O(1) has a more favorable growth trend.
For small inputs, however, constant overhead can also affect speed. Complexity is not the whole story of actual time in seconds.
What have you learned?
- O(1) means the amount of work does not grow with n.
- O(n) describes approximately linear growth.
- O(n²) describes approximately quadratic growth.
- You cannot determine complexity just by counting loop levels.
- Complexity describes a growth trend, not actual running time.
Next: Why Is Binary Search O(log n)?
Your turn to try
Does printing a fixed 20 times have the same growth trend as printing n times?
Ready? Open to see the explanation
No. Twenty is a fixed amount of work, so it is O(1). Printing n times grows with n, so it is O(n).