Higher-order function types in Typescript - Time & Space Complexity

Time Complexity: Higher-order function types

O(n)

Understanding Time Complexity

We want to see how the time needed changes when using higher-order functions in TypeScript.

How does the program's work grow when the input gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function applyToAll(arr: number[], fn: (x: number) => number): number[] {
  return arr.map(fn);
}

const nums = [1, 2, 3, 4, 5];
const doubled = applyToAll(nums, x => x * 2);
    

This code applies a given function to each item in an array and returns a new array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The map method loops through each element of the array.
• How many times: Once for every element in the input array.

How Execution Grows With Input

As the array gets bigger, the function inside map runs more times.

Input Size (n)	Approx. Operations
10	10 function calls
100	100 function calls
1000	1000 function calls

Pattern observation: The work grows directly with the number of items.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows in a straight line with the input size.

Common Mistake

[X] Wrong: "Using a higher-order function like map makes the code slower by a lot."

[OK] Correct: The main work still depends on how many items you have, not on the function style. The overhead is small compared to looping through all items.

Interview Connect

Understanding how higher-order functions affect time helps you explain your code clearly and shows you know how work grows with input size.

Self-Check

"What if the function passed to map itself contains a loop over the array? How would the time complexity change?"