Algorithms from zero
Big-O notation
In the last lesson, you learned to count steps: the largestOf algorithm takes roughly n steps for a list of n items, while a nested-loop algorithm takes roughly n² steps. But what if you count wrong? What if the exact number is 3n + 5, or 100n + 1000? For large n, does the difference matter? It turns out: no. When n grows large, only the dominant term matters. This is the insight behind Big-O notation.
After this lesson you can read and write Big-O notation (O(1), O(n), O(n²)), explain why we drop constants and lower-order terms, and derive the Big-O of simple code by counting loops and nesting.
Big-O notation is a shorthand for describing how an algorithm’s step count grows as the input size n grows. It ignores constant factors and lower-order terms, focusing only on the dominant behavior.
Here is the key insight: when n is large, the dominant term dominates. Suppose one algorithm takes 2n steps and another takes n steps. Both double when n doubles. Suppose one takes 3n² and another takes n². Both quadruple when n doubles. The constant factor (2 vs 1, or 3 vs 1) does not change the growth rate. We say both are O(n) and O(n²) respectively — the Big-O captures growth, not the exact count.
For example:
- Step count = n − 1 → Big-O is O(n)
- Step count = 3n + 5 → Big-O is O(n)
- Step count = n² / 2 → Big-O is O(n²)
- Step count = 100 → Big-O is O(1)
Why drop constants and small terms? As n grows large, the dominant term overwhelms everything else. Compare:
| n | n | 3n + 100 | n² / 2 | n² |
|---|---|---|---|---|
| 10 | 10 | 130 | 50 | 100 |
| 100 | 100 | 400 | 5,000 | 10,000 |
| 1,000 | 1,000 | 3,100 | 500,000 | 1,000,000 |
| 10,000 | 10,000 | 30,100 | 50,000,000 | 100,000,000 |
At n = 10,000:
- The difference between n and 3n + 100 is small: 10,000 vs 30,100 — both are roughly “linear”.
- The difference between n² / 2 and n² is 50,000,000 vs 100,000,000 — a factor of 2, but both are roughly “quadratic”.
What matters for comparing algorithms is the shape of growth, not the constant. Big-O captures the shape.
We read the notation as:
- O(1) = “big-O of 1” or “constant time” — cost does not grow with n
- O(n) = “big-O of n” or “linear time” — cost grows in proportion to n
- O(n²) = “big-O of n squared” or “quadratic time” — cost grows as the square of n
- O(log n) = “big-O of log n” or “logarithmic time” — cost grows very slowly, like the log of n (more on this later)
Big-O is an upper bound — it describes the worst-case growth. For some algorithms, best-case and average-case differ, but Big-O typically refers to worst-case.
Let us derive the Big-O of real code snippets.
Snippet 1: Single loop
function sumAll(numbers) {
let sum = 0;
for (let i = 0; i < numbers.length; i++) {
sum += numbers[i];
}
return sum;
}The loop runs exactly n times (once per element). Each iteration does 1 addition. Total: roughly n steps. Big-O is O(n).
Snippet 2: Nested loops
function allPairs(numbers) {
let count = 0;
for (let i = 0; i < numbers.length; i++) {
for (let j = 0; j < numbers.length; j++) {
count++;
}
}
return count;
}The outer loop runs n times. For each outer iteration, the inner loop runs n times. Total: n × n = n² iterations. Big-O is O(n²).
Snippet 3: No loop
function getFirst(array) {
return array[0];
}One operation: array access. Does not depend on n. Big-O is O(1).
Snippet 4: Loop inside a condition
function findIndex(array, target) {
for (let i = 0; i < array.length; i++) {
if (array[i] === target) {
return i;
}
}
return -1;
}Worst case: the target is not in the array, so the loop runs all n times. Big-O is O(n) (worst-case).
Watch how the step count scales for a single loop. Trace sumAll on a list of size 3:
1
function sumAll(numbers) {
2
let sum = 0;
3
for (let i = 0; i < numbers.length; i++) {
4
sum += numbers[i];
5
}
6
return sum;
7
}
For n = 3, the loop runs 3 times. For n = 100, it runs 100 times. For any n, it runs exactly n times. This is linear growth — O(n).
Here is the growth of different Big-O classes as input size increases:
Notice:
- O(1) is flat — it never changes, no matter how big n is.
- O(n) is a straight line — double n, double the cost.
- O(n²) is a curve that shoots up — double n, quadruple the cost.
- O(log n) grows very slowly — it is nearly flat even for large n.
- O(n log n) is between linear and quadratic — it grows a bit faster than O(n) but much slower than O(n²).
- O(2ⁿ) explodes — even small increases in n cause the cost to skyrocket.
For practical purposes:
- O(1) and O(log n) are very fast.
- O(n) and O(n log n) are practical even for large inputs.
- O(n²) is acceptable for small to medium inputs (up to thousands of items).
- O(2ⁿ) is impractical except for tiny inputs (up to ~30 items).
The dominant term is what matters. An algorithm with 100n + 50 steps is still O(n) — the 100 constant does not change the shape of growth. An algorithm with n² + 1000n is still O(n²) — the n term is negligible when n is large.
A function takes 5n + 10 steps for input size n. What is its Big-O?
An algorithm has a loop that runs n times, and inside that loop another loop that runs n times. What is the Big-O?
What does O(1) mean?
If n goes from 100 to 1,000, how much does the step count increase for an O(n²) algorithm?
Arrange these Big-O classes from fastest to slowest growth:
- O(2ⁿ)
- O(n²)
- O(n)
- O(1)
Edge cases
What about O(log n) and O(n log n)? These come from dividing the problem in half at each step (binary search) or sorting. Log means logarithm — the base-2 log of 1,000,000 is only about 20. So O(log n) is very fast. O(n log n) is a bit slower than O(n) but much faster than O(n²). These are not the focus of this lesson; the math track covers growth and logarithms in depth.
Common mistake
Confusing O(n) with O(2n). Both are still “linear” — the constant multiplier does not matter. O(3n), O(n), and O(100n) all grow at the same rate (linearly). When the dominant term is n, Big-O is O(n).
Why do we drop constants and small terms when writing Big-O notation?
Big-O notation describes how an algorithm’s cost grows as input size n grows. We drop constant multipliers and lower-order terms, keeping only the dominant term. An algorithm taking 3n + 100 steps is O(n); one taking n² / 2 steps is O(n²). Common classes are:
- O(1) — constant time, cost does not grow
- O(log n) — logarithmic, grows very slowly
- O(n) — linear, cost grows in proportion to n
- O(n log n) — a bit faster than O(n²)
- O(n²) — quadratic, cost grows as the square of n
- O(2ⁿ) — exponential, grows explosively
To find the Big-O of code: count the loops. A single loop over n items is O(n). Nested loops are O(n²). No loop is O(1). The dominant term is what counts.