Every pattern in this piece gets judged by the same yardstick: how its running time and memory grow as the input grows, not how fast it happens to run on today's laptop against today's input size. That's what Big-O notation actually measures — the shape of the growth curve, with constant factors and lower-order terms thrown away, because those are exactly the details that stop mattering once n gets large enough.
function hasDuplicate(arr) { // O(n) time, O(n) space
const seen = new Set();
for (const x of arr) { // one pass, n iterations
if (seen.has(x)) return true; // O(1) average per check
seen.add(x);
}
return false;
}
function hasDuplicateBruteForce(arr) { // O(n^2) time, O(1) space
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) { // inner loop re-runs for every outer iteration
if (arr[i] === arr[j]) return true;
}
}
return false;
}
Two loops that run one after another add: O(n) + O(n) is O(2n), which simplifies to O(n) — Big-O drops constant multipliers because they don't change the shape of the curve as n grows. Two loops where one runs inside the other multiply: an outer loop of n iterations wrapping an inner loop of n iterations does n × n work, which is O(n²), not O(n) + O(n). That distinction — "do these loops run one after another, or does one run inside the other" — is the single most common thing to get wrong when eyeballing complexity from code, and it's usually the first question worth asking about any block of nested loops you're handed.
| Complexity | Name | Concrete example |
|---|---|---|
| O(1) | Constant | array index access, hash map get/set |
| O(log n) | Logarithmic | binary search, balanced BST insert/lookup |
| O(n) | Linear | a single pass over an array |
| O(n log n) | Linearithmic | comparison-based sorting (merge sort, heapsort) |
| O(n²) | Quadratic | a nested loop comparing every pair of elements |
| O(2ⁿ) | Exponential | naive recursive Fibonacci, generating every subset |
| O(n!) | Factorial | generating every permutation |
function fib(n) { // O(2^n) — every call spawns two more calls
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); // no caching: massive repeated work, covered in the DP chapters
}
O(log n) shows up specifically when each step throws away a constant fraction of the remaining work — binary search halves the search space every comparison, so the number of comparisons needed to shrink n items down to 1 is log₂ n. That's a genuinely different growth curve from O(n): doubling the input size adds only one more step to an O(log n) algorithm, versus doubling the total work for an O(n) one.
push is "O(1) amortized"A dynamic array — JavaScript's Array, really every language's growable list under the hood — doesn't resize on every single append. It over-allocates, and only grows its backing storage when it's actually full, typically by doubling:
// Conceptually, a dynamic array's push does this under the hood:
function push(dynArray, value) {
if (dynArray.length === dynArray.capacity) {
resizeTo(dynArray, dynArray.capacity * 2); // O(n) — copies every existing element — but RARE
}
dynArray[dynArray.length++] = value; // O(1) — happens on every single call
}
Look at a single push in isolation and the worst case is O(n) — the one that happens to trigger a resize. But spread that resize cost across the whole sequence of pushes that led up to it, and the picture changes: doubling means the total copying work across n pushes sums to roughly n + n/2 + n/4 + n/8 + ... < 2n. Divide that by n pushes and each one only costs a constant amount of copying on average, even though any individual push might be the expensive one. That average-cost-over-a-sequence argument is exactly what "amortized" means — it's a claim about the total cost of many operations, not a guarantee about any single one. This is also why interviewers accept "push is O(1) amortized" as the right answer, not "O(1)" outright — the distinction between worst-case and amortized cost is precise and worth stating exactly.
One more thing worth internalizing here since it comes up in nearly every later chapter: recursion's call stack counts as space, not just the variables you explicitly allocate. A recursive function that goes n levels deep before hitting its base case is using O(n) space on the call stack alone, even if it never allocates a single array — that's why a deeply recursive solution to a problem an iterative loop could solve in O(1) space is a real, measurable trade-off, not just a style choice.