Quick Overview
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
When building scalable software, measuring execution speed in seconds is unreliable because hardware speeds vary. Big O Notation provides a mathematical framework to measure how an algorithm's runtime and memory requirements grow as the input size (N) approaches infinity.
Here is the asymptotic efficiency spectrum from best to worst:
O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) < O(N!)
[Instant] [Sub-linear] [Linear] [Log-linear] [Quadratic] [Exponential]
Operations
▲
│ / O(2^N)
│ /
│ / O(N^2)
│ /
│ . - ' O(N log N)
│ . - '
│ . - ' O(N)
│ . - '
│ . -' O(log N)
│─────────────────────────── O(1)
└───────────────────────────────────────► Input Size (N)
// O(1) Constant Time: Array index lookup
function getFirst(arr) {
return arr[0];
}
// O(N) Linear Time: Single loop through array
function findMax(arr) {
let max = -Infinity;
for (const num of arr) {
if (num > max) max = num;
}
return max;
}
// O(N^2) Quadratic Time: Nested loops (e.g. Pair comparison)
function printAllPairs(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
console.log(arr[i], arr[j]);
}
}
}
arr.includes() or str.slice() take O(N) time under the hood even if written on one line.Mastering Big O enables intelligent algorithmic trade-offs. Next, let's explore Dynamic Arrays and Amortized Resizing!
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.
Two pointers moving at different speeds must eventually meet inside a loop, the way a faster runner laps a slower one. That detects a cycle in `O(N)` time and `O(1)` space, with no visited set.