Big O Notation — Time & Space Complexity
Master Big O notation — O(1) to O(n!), time and space complexity, loop patterns, recurrence relations, growth chart, and an interactive complexity explorer with interview-ready examples.
Introduction
Big O notation describes how an algorithm's time or space requirements grow as input size
n increases. It answers: "If I double the data, does runtime double, explode, or stay flat?" — the single most
important lens for writing scalable code and passing technical interviews.
This guide covers:
- What Big O measures — worst-case growth, not exact milliseconds
- Complexity hierarchy — O(1) through O(n!)
- Time complexity patterns — loops, halving, recursion
- Space complexity — auxiliary memory and call stack
- Interactive explorer — toggle curves and match code patterns
- Rules of thumb — drop constants, compare algorithms
Quick index
1. What is Big O?
Big O expresses an upper bound on growth rate. We keep the dominant term and drop constants and lower-order terms.
| Expression | Simplified Big O | Why |
|---|---|---|
3n + 5 | O(n) | Drop constant 3 and lower term 5 |
n² + n + 100 | O(n²) | n² dominates as n grows |
2ⁿ + n³ | O(2ⁿ) | Exponential beats polynomial |
// O(n) — one pass
function findMax(arr) {
let max = arr[0]
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) max = arr[i]
}
return max
}
// O(1) — hash lookup (average case)
function hasUser(map, id) {
return map.has(id)
}2. Complexity hierarchy
From fastest to slowest growth — memorize this order:
| Big O | Name | n = 10 | n = 100 | Rating |
|---|---|---|---|---|
| O(1) | Constant | 1 | 1 | Excellent |
| O(log n) | Logarithmic | ~3 | ~7 | Good |
| O(n) | Linear | 10 | 100 | Fair |
| O(n log n) | Linearithmic | ~33 | ~664 | Bad |
| O(n²) | Quadratic | 100 | 10,000 | Horrible |
| O(2ⁿ) | Exponential | 1,024 | ≈ 1.27×10³⁰ | Horrible |
| O(n!) | Factorial | 3,628,800 | astronomically large | Horrible |
3. Big O growth chart
The chart below shows how operations (y-axis) scale as elements (x-axis) grow. Flat lines stay cheap; steep curves become bottlenecks.
| Region | Complexities | Real-world feel |
|---|---|---|
| Excellent | O(1) | Same cost at any scale |
| Good | O(log n) | Barely notices 10× data |
| Fair | O(n) | Doubles when data doubles |
| Bad | O(n log n) | Sorting-scale — usually fine |
| Horrible | O(n²), O(2ⁿ), O(n!) | Breaks at thousands+ elements |
4. Interactive explorer
Toggle complexity curves, drag n, and click code patterns to see operation counts update in real time.
Big O Complexity Explorer
Toggle curves, drag n, and click code patterns to see how operations scale. Y-axis uses log scale.
Operations at n = 10
Time complexity patterns — click to highlight
5. Full implementation
// O(1) — hash map lookup
function hasUser(usersById, id) {
return usersById[id] !== undefined
}
// O(n) — single pass
function findMax(arr) {
let max = arr[0]
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) max = arr[i]
}
return max
}
// O(n²) — nested loops
function hasDuplicateNaive(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) return true
}
}
return false
}
// O(n) — hash set
function hasDuplicateSet(arr) {
const seen = new Set()
for (const v of arr) {
if (seen.has(v)) return true
seen.add(v)
}
return false
}Function calls with output
// ── Demo calls — output shown on the right ──
const users = { u1: 'Alice', u2: 'Bob' }
hasUser(users, 'u1') // → true
findMax([3, 9, 2, 7]) // → 9
hasDuplicateNaive([1, 2, 1]) // → true
hasDuplicateSet([1, 2, 3, 4]) // → false6. Time complexity patterns
Map code structure to Big O — the pattern table every interview expects.
| Pattern | Code shape | Time complexity |
|---|---|---|
| Single loop | for (i = 0; i < n; i++) | O(n) |
| Nested full | for i × for j < n | O(n²) |
| Nested triangle | for j < i | O(n²) |
| Halving / doubling | i *= 2 or n /= 2 | O(log n) |
| Half range | i < n/2 | O(n) — constants drop |
| Sequential loops | two for n back-to-back | O(n) — not O(n²) |
| Linear recursion | T(n) = T(n-1) + O(1) | O(n) |
| Divide & conquer | T(n) = 2T(n/2) + O(n) | O(n log n) |
| Fibonacci recursion | T(n) = T(n-1) + T(n-2) | O(2ⁿ) |
O(n) — single loop
function sumArray(arr) {
let total = 0
for (let i = 0; i < arr.length; i++) {
total += arr[i]
}
return total
}O(n²) — nested loops
function hasDuplicatePair(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) return true
}
}
return false
}O(n²) Nested Loop Grid
Each highlighted cell = one inner-loop iteration. n × n cells = O(n²) operations.
Outer i: — · Comparisons so far: 0 / 36
for (let i = 0; i < 6; i++) {
for (let j = 0; j < 6; j++) {
// 36 total iterations → O(n²)
}
}Each grid cell is one inner-loop iteration — n × n = O(n²) comparisons.
O(n + k) — scatter & gather (bucket / counting sort)
One pass to count frequencies, one pass to output — linear when value range k is small. See the full step visualizer: Counting Sort.
// Count occurrences — O(n)
for (const num of arr) buckets[num]++
// Gather in order — O(n + k)
for (let v = 0; v <= maxVal; v++) {
while (buckets[v]--) sorted.push(v)
}O(log n) — halving
function binarySearch(arr, target) {
let lo = 0
let hi = arr.length - 1
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2)
if (arr[mid] === target) return mid
if (arr[mid] < target) lo = mid + 1
else hi = mid - 1
}
return -1
}O(n log n) — merge sort recurrence
function mergeSort(arr) {
if (arr.length <= 1) return arr
const mid = Math.floor(arr.length / 2)
const left = mergeSort(arr.slice(0, mid))
const right = mergeSort(arr.slice(mid))
return merge(left, right) // O(n) merge × log n levels
}7. Space complexity
Space complexity measures extra memory an algorithm uses — variables, data structures, and the call stack for recursion.
| Big O | Example | What uses memory |
|---|---|---|
| O(1) | Iterative binary search | Fixed pointers lo, hi, mid |
| O(log n) | Recursive binary search | Call stack depth log n |
| O(n) | Copy input to new array | arr.slice(), result buffer |
| O(n) | Recursive factorial / linear DFS | Stack depth n |
| O(n²) | 2D DP table n × n | Matrix for all-pairs paths |
// O(1) space — in-place swap
function reverseInPlace(arr) {
let i = 0
let j = arr.length - 1
while (i < j) {
;[arr[i], arr[j]] = [arr[j], arr[i]]
i++
j--
}
}
// O(n) space — new array
function doubleValues(arr) {
return arr.map((x) => x * 2)
}
// O(n) stack space — naive recursive sum
function recursiveSum(arr, i = 0) {
if (i >= arr.length) return 0
return arr[i] + recursiveSum(arr, i + 1)
}8. Analyzing code step by step
Use this checklist on any snippet:
- Identify the input size — usually
n = array.length - Count nested loops — each level multiplies complexity
- Check loop bounds — halving → log; triangle inner → still n²
- Account for recursion — depth × work per call
- Drop constants —
n/2,3n,100→ O(n) - Keep the dominant term — n² + n → O(n²)
function example(n) {
let count = 0
for (let i = 0; i < n; i++) {
count++
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
count++
}
}
return count
}
// Loop 1: O(n)
// Loop 2: O(n²) — nested
// Total: O(n + n²) → O(n²)9. Common algorithm complexities
| Algorithm / operation | Time | Space |
|---|---|---|
| Array index access | O(1) | O(1) |
| Array push (amortized) | O(1) | O(1) |
| Linear search | O(n) | O(1) |
| Binary search | O(log n) | O(1) iterative |
| Bubble / insertion sort | O(n²) | O(1) |
| Counting / bucket sort | O(n + k) | O(n + k) |
| Merge sort | O(n log n) | O(n) |
| Quick sort (average) | O(n log n) | O(log n) stack |
| Hash map get/set (avg) | O(1) | O(n) storage |
| BFS / DFS (graph) | O(V + E) | O(V) |
| Dijkstra (binary heap) | O((V + E) log V) | O(V) |
// O(1) average — Map for frequency count
function charFrequency(s) {
const freq = new Map()
for (const ch of s) {
freq.set(ch, (freq.get(ch) ?? 0) + 1)
}
return freq
}10. Rules & pitfalls
| Rule | Example |
|---|---|
| Drop constants | O(2n) → O(n) |
| Drop lower terms | O(n² + n) → O(n²) |
| Different inputs use different vars | O(a + b), not O(n) if two arrays |
| Nested → multiply | O(n × m) for n × m grid |
| Sequential → add, keep max | O(n) + O(n²) → O(n²) |
| Best vs worst vs average | Binary search worst O(log n); quicksort worst O(n²) |
Common mistakes
| Mistake | Reality |
|---|---|
| "Two loops = O(n²)" | Only if nested |
| "Recursion is always O(n)" | Can be O(2ⁿ) — check branching factor |
| "Big O is exact runtime" | It's growth class, not milliseconds |
| Ignoring space | O(n log n) time may still need O(n) space |
11. Real-life examples
| Scenario | Complexity | Why it matters |
|---|---|---|
| Database index lookup | O(log n) | B-tree index on 10M rows → ~23 hops, not 10M scans |
| Nested React renders | O(n²) | Rendering a list inside a list without memoization |
| HashMap user lookup | O(1) avg | usersById[id] vs scanning entire user array |
| Brute-force password crack | O(2ⁿ) | Each added character doubles search space |
| Merge two sorted CSV exports | O(n + m) | Linear merge — same idea as merge sort's merge step |
Signup duplicate-email check
HashSet gives O(n) duplicate detection; nested loops would be O(n²) and fail at scale.
users = 5 signups
alice@x.com, bob@y.com, alice@x.com, carol@z.com, bob@y.com
5 signups — one duplicate email to catch.
Real-world implementation
function findDuplicateEmails(users) {
const seen = new Set()
const duplicates = []
for (const user of users) {
const email = user.email.toLowerCase()
if (seen.has(email)) duplicates.push(email)
else seen.add(email)
}
return duplicates
}
function findDuplicateEmailsNaive(users) {
const duplicates = []
for (let i = 0; i < users.length; i++) {
for (let j = i + 1; j < users.length; j++) {
if (users[i].email === users[j].email) duplicates.push(users[i].email)
}
}
return [...new Set(duplicates)]
}Full working code for the scenario above.
Function calls with output
// ── Function calls with output ──
const users = [
{ email: "alice@x.com" },
{ email: "bob@y.com" },
{ email: "alice@x.com" }, // duplicate
{ email: "carol@z.com" },
{ email: "bob@y.com" }, // duplicate
]Side output shows return value after each call — step through to trace execution.
Summary
| Concept | Takeaway |
|---|---|
| Big O | Upper bound on growth as n increases |
| Time | How operations scale — loops, recursion, divides |
| Space | Extra memory + call stack depth |
| Goal | Excellent/Good/Fair for large n; avoid Horrible at scale |
Big O is the vocabulary for comparing algorithms before writing code. Use the growth chart for intuition, the interactive explorer for pattern matching, and the hierarchy table for interviews.
Next reads: Counting Sort — Visualized for scatter/gather step breakdown, JavaScript Arrays for built-in method complexities, and System Design Fundamentals for scaling beyond single-machine algorithms.
Subscribe to my newsletter
Stay up to date and get notified when I share new contents.
No spam ever, unsubscribe anytime