Cut the Problem in Half
O(log n) means logarithmic time: every step cuts the remaining work in half. Because halving shrinks numbers so fast, doubling the input adds only one extra step.
16 elements need 4 halvings, 32 elements need 5, a million elements about 20, a billion about 30. That is why logarithmic algorithms feel instant even on huge data.
The classic example is binary search — but it only works on sorted data. Halving needs an order to know which half to throw away.
A Halving Loop
The simplest way to see O(log n) is a loop that divides n by 2 until it reaches 1. The number of rounds is the logarithm of n: for n = 16 the loop runs 4 times, because 2 · 2 · 2 · 2 = 16.
Halving until one remains
16 becomes 8, 4, 2, 1 — four steps. Doubling n to 32 would add just one more step.
Output: TypeScript file and captured output
let n = 16
let steps = 0
while (n > 1) {
n = Math.floor(n / 2)
steps++
console.log("n is now", n)
}
console.log("16 became 1 in", steps, "steps")
Binary Search
Binary search finds a value in a sorted array by always checking the middle element. If the middle is too small, the whole left half is thrown away; if too big, the right half. Each check halves the search range.
Two markers, lo and hi, hold the current range. The loop ends when the value is found or the range is empty.
TypeScript has no binary search of its own. The built-in lookups — indexOf() and includes() — walk the array from the start, so they stay O(n) even when the data is already sorted. On sorted data the hand-written loop is the faster one.
Binary search step by step
In a sorted array of 16 numbers, the search for 13 needs only 4 checks: the range shrinks 16 → 8 → 4 → 2 and lands on index 6. A linear search would have needed 7 steps here — and up to 16.
Output: TypeScript file and captured output
const nums = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31]
const target = 13
let steps = 0
let lo = 0
let hi = nums.length - 1
while (lo <= hi) {
steps++
const mid = Math.floor((lo + hi) / 2)
if (nums[mid] === target) {
console.log("found", target, "at index", mid, "after", steps, "checks")
break
}
if (nums[mid] < target) {
lo = mid + 1
} else {
hi = mid - 1
}
}
The built-in lookup is still linear
Both lookups agree: 9 sits at index 4. But indexOf() gets there by testing 5 elements, while the binary search needs 3 checks. For the missing value 10, indexOf() tests all 8 elements and returns -1; the binary search stops after 3 checks and can even report index 5 — the place where 10 would fit to keep the array sorted.
With 8 elements the difference is small. With a million it is about 1,000,000 steps against 20.
Output: TypeScript file and captured output
const nums = [1, 3, 5, 7, 9, 11, 13, 15]
// How many elements the built-in scan has to touch: it walks from the start.
function scanned(xs: number[], target: number): number {
let steps = 0
xs.findIndex((x) => {
steps++
return x === target
})
return steps
}
interface Found {
index: number
checks: number
insertAt: number
}
// The hand-written binary search: every check halves the range.
function binarySearch(xs: number[], target: number): Found {
let lo = 0
let hi = xs.length - 1
let checks = 0
while (lo <= hi) {
checks++
const mid = Math.floor((lo + hi) / 2)
if (xs[mid] === target) {
return { index: mid, checks, insertAt: mid }
}
if (xs[mid] < target) {
lo = mid + 1
} else {
hi = mid - 1
}
}
return { index: -1, checks, insertAt: lo }
}
for (const target of [9, 10]) {
console.log("target", target)
console.log(" indexOf:", nums.indexOf(target), "includes:", nums.includes(target),
"- scanned", scanned(nums, target), "of", nums.length, "elements")
const hit = binarySearch(nums, target)
if (hit.index >= 0) {
console.log(" binary search: index", hit.index, "after", hit.checks, "checks")
} else {
console.log(" binary search: not found after", hit.checks, "checks -",
target, "would fit at index", hit.insertAt)
}
}
O(n log n): Sorting
O(n log n) sits between linear and quadratic and is the complexity of good sorting algorithms: the data is halved again and again (log n levels), and each level does a linear amount of work (n).
You rarely write a sort yourself — every array already has sort(), and it is O(n log n). Sorting once, then binary-searching many times, is a common and fast pattern.
Sort an array
nums.sort((a, b) => a - b) orders the 8 numbers in about 8 · log 8 = 24 steps — far fewer than the 64 a quadratic sort would use, and the gap widens fast as the array grows.
The comparator is not optional here. Called without one, sort() compares the values as text: "13" starts with a 1, so it lands before "5". The program prints both orders.
Output: TypeScript file and captured output
const nums = [31, 5, 17, 1, 23, 9, 27, 13]
const show = (xs: number[]): string => `[ ${xs.join(", ")} ]`
// Without a comparator, sort() compares the values as text.
console.log("as text: ", show([...nums].sort()))
// With a numeric comparator the order is the one we want.
console.log("as numbers:", show([...nums].sort((a, b) => a - b)))