Why method costs matter
When you work out the time complexity of a function, you count the work done by every line, including calls to methods of arrays and strings. A call such as nums.shift() looks like a single step, yet it can touch every element. This reading lists the costs of the most common array and string methods in TypeScript, so you can add them up correctly.
Below, n is the length of the array or string the method is called on. The costs are those you should assume when reasoning about worst cases. Real engines have optimisations, but they don't change the picture you need for interview-style analysis.
Array methods
| Operation | Time | Notes |
|---|---|---|
nums[i], nums[i] = v, nums.length | O(1) | Direct access by position |
push(v), pop() | O(1) | Work at the end; amortised |
shift(), unshift(v) | O(n) | Every other element changes position |
splice(i, k, ...) | O(n) | Elements after i may move |
slice(a, b), concat(other), [...nums] | O(n) | Build a new array |
indexOf(v), includes(v) | O(n) | Linear search |
join(sep), reverse() | O(n) | Visit every element |
sort(compare) | O(n log n) | Sorts in place |
Here is what the end operations and the front operations do to a small array:
const a = [1, 2, 3, 4];
a.push(5);
console.log(a); // [ 1, 2, 3, 4, 5 ]
console.log(a.pop(), a); // 5 [ 1, 2, 3, 4 ]
console.log(a.shift(), a); // 1 [ 2, 3, 4 ]
a.unshift(0);
console.log(a); // [ 0, 2, 3, 4 ]
a.splice(1, 1); // remove one element at index 1
console.log(a); // [ 0, 3, 4 ]
Removing from the front shifts everything else one place to the left. Each shift may move up to n - 1 elements, and a loop that empties an array from the front this way does about n²/2 element moves in total. Counting the moves gives 10 for an array of 5 elements and 45 for an array of 10. Taking elements from the end with pop costs O(1) each, so when order allows it, work from the end, or move an index forward instead of deleting.
Note which methods change the array and which return a new one. push, pop, shift, unshift, splice, reverse and sort change the array they are called on. slice, concat, map and filter leave it alone and build a new one.
String methods
Strings in TypeScript are immutable: no method changes a string, every method that seems to change it returns a new one. The compiler even reports an error if you try to assign to a character, as in s[0] = "z".
| Operation | Time | Notes |
|---|---|---|
s.length, s[i], s.charAt(i), s.at(i) | O(1) | Access by position |
s.slice(a, b), s.substring(a) | O(n) | Treat as copying the piece |
s.indexOf(t), s.includes(t) | O(n) or more | Searches for a pattern |
s.toUpperCase(), s.repeat(k) | O(n) for the result | Create a new string |
s.split(sep) | O(n) | Creates an array of pieces |
a + b | O(a.length + b.length) | Treat as a new string |
const s = "hello world";
console.log(s.length, s[0], s.charAt(4), s.at(-1)); // 11 h o d
console.log(s.slice(0, 5), s.substring(6)); // hello world
console.log(s.indexOf("o"), s.includes("wor")); // 4 true
console.log(s.split(" ")); // [ 'hello', 'world' ]
let t = "abc";
const up = t.toUpperCase();
console.log(t, up); // abc ABC
The original t is still "abc" after toUpperCase(), and the result is a separate string.
A substring search such as indexOf can be more than O(n). Comparing a pattern of length m against each position of a string of length n gives O(n * m) in the simple approach. When the pattern is short, you can treat this as O(n).
Building strings and arrays in loops
Two habits keep loops from becoming quadratic:
- Collect pieces, then join once. Adding to a string with
+=in a loop conceptually creates a new string each time. Some engines optimise this, but pushing the pieces into an array and callingjoin("")once is alwaysO(total length). - Don't call a linear method inside a loop over the same data. A loop that runs
ntimes and callsincludes,indexOf,sliceorshifteach time isO(n²).
const parts: string[] = [];
for (let i = 0; i < 5; i++) {
parts.push(String(i));
}
console.log(parts.join("")); // 01234
console.log("abc".split("").reverse().join("")); // cba
The last line chains three O(n) methods: split, reverse and join. Chained calls add up, so the whole expression is O(n), and it uses O(n) extra space for the temporary array.
Gotchas
- Compare numbers with a comparator.
[10, 9, 1].sort()compares the elements as strings and gives[1, 10, 9]. Writesort((x, y) => x - y)to get[1, 9, 10]. - Methods on a copy cost a copy. Calling
[...nums].sort(...)to protect the original adds anO(n)copy andO(n)space. - Strings compare in
O(n)as well. The expressiona === bon two long equal strings has to examine their characters, so it isn't always a constant-time step. - Types do not change the cost. Annotations like
string[]are erased when compiling to JavaScript, and the run-time work is the same with or without them.
Key takeaways
- Index access,
length,pushandpopareO(1). shift,unshift,splice,slice,concat,indexOfandincludesareO(n).sortisO(n log n).- Strings never change in place; operations that build new strings cost time proportional to the result.
- A linear method inside a loop over the same data makes the loop quadratic.