Big O and Complexity
Big O Notation Explained
Written by Swapnil RajaPublished
Big O does not tell you how fast your code is. It tells you how much worse it gets when the input grows - which is the thing that actually breaks in production.
What it measures
Big O answers one question: if the input doubles, what happens to the work?
It deliberately ignores hardware, language and constants. A fast machine changes the milliseconds; it does not change the shape.
Reading it off the code
Four shapes
javascript
// O(1) — constant. Input size is irrelevant.
function first(items) {
return items[0]
}
// O(n) — linear. Double the input, double the work.
function sum(items) {
let total = 0
for (const n of items) total += n
return total
}
// O(n²) — quadratic. Double the input, four times the work.
function hasDuplicate(items) {
for (let i = 0; i < items.length; i++) {
for (let j = i + 1; j < items.length; j++) {
if (items[i] === items[j]) return true
}
}
return false
}
// O(log n) — halves the problem each step.
function binarySearch(sorted, target) {
let low = 0
let high = sorted.length - 1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
if (sorted[mid] === target) return mid
if (sorted[mid] < target) low = mid + 1
else high = mid - 1
}
return -1
}