Start learning free

TYPESCRIPT · BIG O NOTATION

Time Complexity Practice 1 in TypeScript, explained

Built-in does not mean free

TypeScript, like JavaScript, comes with many ready-made functions and methods: Math.max, includes, indexOf, map, filter, sort, Object.keys and more. One short line of code can hide a loop over the whole input. When you analyse the time complexity of your own function, the cost of each built-in call has to be counted too.

A good habit is to ask for each built-in call: does it look at only one element, or at all of them? If it can look at all n elements and it sits inside a loop that also runs n times, the total is O(n²), even though the code has no visible nested loop.

Built-ins that look at every element

These methods have to visit the elements of an array one by one, so each call is O(n), where n is the length of the array:

  • includes(x) and indexOf(x) compare against elements until they find a match or reach the end.
  • map, filter, forEach and reduce call your callback once for each element.
  • Math.max(...nums) and Math.min(...nums) read every number.
  • [...nums] and nums.slice() copy every element.
  • Object.keys(obj), Object.values(obj) and Object.entries(obj) build an array with one item per property.
const nums = [4, 9, 2, 7];

console.log(Math.max(...nums), Math.min(...nums)); // 9 2

let calls = 0;
const doubled = nums.map(x => {
  calls++;
  return x * 2;
});
console.log(doubled, calls); // [ 8, 18, 4, 14 ] 4

The callback ran 4 times for 4 elements. With a million elements it would run a million times. The cost of the callback itself multiplies this: a callback that does O(1) work gives O(n) overall, and a callback that calls includes on another array of size m gives O(n * m).

Some of these methods can stop early. some, find, includes and indexOf stop at the first match. For nums.some(x => x === 9) on the array above, the callback runs only twice. The worst case is still O(n), which happens when there is no match: nums.includes(100) has to check all four elements and returns false.

Sorting

The sort method takes O(n log n) time in general, since it compares elements and the number of comparisons grows slightly faster than n. It sorts the array in place and returns the same array. Two points trip people up:

  • The default order is alphabetical. With no comparator, sort converts the elements to strings, so [10, 9, 1].sort() gives [1, 10, 9]. Use sort((a, b) => a - b) for numbers, which gives [1, 9, 10].
  • The array is changed. If you need the original order afterwards, copy it first with [...nums].sort(...), which costs an extra O(n).

Sorting is often worth its cost. It can turn a pair-comparing O(n²) solution into O(n log n), but it is not free in a place where one pass would do. Finding the maximum with Math.max or one loop is O(n), which beats sorting just to read the last element.

A hidden loop inside a loop

Here is a function that checks whether an array contains a duplicate. Both versions are correct, and they differ in how much work they do:

function hasDuplicateSlow(a: number[]): boolean {
  for (let i = 0; i < a.length; i++) {
    if (a.indexOf(a[i]) !== i) {
      return true;
    }
  }
  return false;
}

function hasDuplicateFast(a: number[]): boolean {
  const seen = new Set<number>();
  for (const x of a) {
    if (seen.has(x)) {
      return true;
    }
    seen.add(x);
  }
  return false;
}

console.log(hasDuplicateSlow([1, 2, 3, 2])); // true
console.log(hasDuplicateFast([1, 2, 3, 2])); // true
console.log(hasDuplicateFast([1, 2, 3]));    // false

In hasDuplicateSlow, the loop runs up to n times and each indexOf scans up to n elements, so the worst case is O(n²). In hasDuplicateFast, each has and add on a Set takes constant time on average, so the loop is O(n) overall. The price is O(n) extra space for the set.

A Set also removes duplicates in one step: [...new Set([1, 2, 2, 3])] gives [1, 2, 3], in O(n) time.

Gotchas

  • Spreading a huge array into a call. Math.max(...nums) passes every element as an argument. For an array with hundreds of thousands of elements, this can throw a RangeError. In a test run on Node 22, an array of 200,000 numbers failed. For large inputs use reduce or a loop instead, which scan the array without that limit.
  • Copies cost time and space. slice, spread and concat are O(n) and allocate a new array. Doing one inside a loop multiplies the cost.
  • The callback counts. The complexity of map or filter is the number of elements times the cost of one callback call.
  • Annotations do not speed anything up. Types like number[] are erased when TypeScript compiles to JavaScript. The cost of a built-in call depends only on what it does at run time.

Key takeaways

  • A built-in call can hide a loop; count its cost like any other loop.
  • includes, indexOf, map, filter, reduce, spread and slice are O(n).
  • sort is O(n log n), sorts as strings by default and changes the array.
  • A Set or Map replaces repeated O(n) searches with O(1) average lookups.
Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free