What time complexity measures
Time complexity describes how the work a function does grows as its input grows. It doesn't measure seconds. The same code runs faster on a newer laptop or a different runtime, so seconds say more about the machine than about the code. Instead, you count the basic steps the code takes, such as assignments, comparisons and additions, as a function of the input size, usually called n.
Take a function that adds up an array:
function sum(nums: number[]): number {
let total = 0;
for (const x of nums) {
total += x;
}
return total;
}
console.log(sum([3, 1, 4, 1, 5])); // 14
Here n is nums.length. The function sets total once, runs the loop body n times and returns once: roughly n + 2 steps. Give it twice as many numbers and it does about twice the work. That proportional growth is the important fact, and Big O notation is the way to write it down.
Big O notation
Big O keeps only the part of the step count that dominates as n gets large. Two rules get you there:
- Drop constant factors.
3nandnboth grow in a straight line, so both areO(n). - Drop lower-order terms. In
n + 2, the2stops mattering oncenis in the thousands, sosumisO(n). In the same way,n² + nisO(n²).
Constants are dropped because they depend on details Big O deliberately ignores: the engine, the hardware, how many machine instructions one line becomes. What survives is the shape of the growth, and that's what decides whether code still works when the input is a million elements instead of ten.
Big O usually describes the worst case. A search can get lucky:
function indexOfValue(nums: number[], target: number): number {
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) {
return i;
}
}
return -1;
}
console.log(indexOfValue([3, 1, 4, 1, 5], 4)); // 2
console.log(indexOfValue([3, 1, 4], 9)); // -1
If target is the first element, the loop stops after one step. If it isn't in the array, the loop checks all n elements. Since you can't count on luck, this function is O(n).
Linear time, O(n)
A function runs in linear time when its work grows in direct proportion to n. The typical shape is a loop that visits each element once and does a fixed amount of work per element: summing, counting, finding the largest value or checking whether a value is present.
Some loops look different but are still linear:
- Two loops one after the other take about
2nsteps, which is stillO(n). Sequential pieces add up; they don't multiply. - A loop that skips elements, such as
i += 2, takes aboutn / 2steps: alsoO(n).
function minAndMax(nums: number[]): [number, number] {
let min = nums[0];
for (const x of nums) {
if (x < min) min = x;
}
let max = nums[0];
for (const x of nums) {
if (x > max) max = x;
}
return [min, max];
}
console.log(minAndMax([3, 1, 4, 1, 5])); // [ 1, 5 ]
Compare linear time with its neighbours. Reading nums[i] or nums.length takes the same time whatever the size of the array: that is constant time, O(1). A loop nested inside another loop over the same array does up to n steps for each of n elements: that is quadratic time, O(n²). The gap between them grows fast:
| n | O(1) | O(n) | O(n²) |
|---|---|---|---|
| 10 | 1 | 10 | 100 |
| 1,000 | 1 | 1,000 | 1,000,000 |
| 1,000,000 | 1 | 1,000,000 | 1,000,000,000,000 |
A million basic steps finish in a blink. A trillion take far too long for any test to wait for.
Hidden loops in TypeScript code
Not every loop is written as for. Many array and string methods walk through their input internally, so each call costs O(n) by itself: includes, indexOf, find, filter, map, reduce, join and split, plus copies such as slice and the spread syntax [...nums]. A single call is fine. Putting one inside a loop multiplies the costs:
// O(n²): slice and includes each scan up to n elements, n times
function hasDuplicateSlow(nums: number[]): boolean {
for (let i = 0; i < nums.length; i++) {
if (nums.slice(i + 1).includes(nums[i])) {
return true;
}
}
return false;
}
// O(n): one pass, with Set lookups that take constant time on average
function hasDuplicate(nums: number[]): boolean {
const seen = new Set<number>();
for (const x of nums) {
if (seen.has(x)) {
return true;
}
seen.add(x);
}
return false;
}
Both functions give the same answers, but only the second stays linear. It trades a little memory, the Set, for a lot of time.
One TypeScript-specific point: type annotations cost nothing at run time. The compiler checks them and then removes them, so number[] or Set<number> never changes how fast the code runs. Complexity depends only on what the code does.
Using it in this chapter
Coding problems often name a target, such as "your algorithm should run in O(n) time", and you'll need to check your own code against it. A reliable routine:
- Decide what
nis: usually the length of the input array or string. - Find every loop, including the hidden ones inside built-in methods.
- Add the costs of pieces that run one after another, and multiply the costs of pieces nested inside each other.
- Drop constant factors and lower-order terms.
Apply it to minAndMax: two sequential loops over n elements give n + n = 2n, which is O(n). Apply it to hasDuplicateSlow: a loop of n iterations, each doing up to n steps of copying and searching, gives O(n²). With that habit, telling a linear solution from a quadratic one becomes a quick read of the code, which is exactly what the rest of this chapter builds on.