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?"

Practice

1. What is a higher-order function type in TypeScript?

easy

A. A function type that takes or returns another function

B. A function type that only returns a number

C. A function type that cannot accept parameters

D. A function type that only works with strings

Solution

1. Step 1: Understand function types

   Function types describe the input and output of functions in TypeScript.

2. Step 2: Define higher-order function types

   Higher-order function types specifically involve functions that take other functions as parameters or return functions.

3. Final Answer:

   A function type that takes or returns another function -> Option A

4. Quick Check:

   Higher-order function = function takes/returns function [OK]

Hint: Higher-order means function uses another function [OK]

Common Mistakes:

• Thinking higher-order means only returning numbers
• Confusing higher-order with no parameters
• Assuming it only works with strings

2. Which of the following is the correct TypeScript syntax for a higher-order function type that takes a function returning number and returns void?

easy

A. (fn: number) => void

B. fn: () => number => void

C. () => number => void

D. (fn: () => number) => void

Solution

1. Step 1: Analyze the parameter type

   The parameter is a function with no arguments returning a number, written as () => number.

2. Step 2: Analyze the return type

   The higher-order function returns void, so the full type is (fn: () => number) => void.

3. Final Answer:

   (fn: () => number) => void -> Option D

4. Quick Check:

   Parameter is function, return is void [OK]

Hint: Use parentheses to wrap function parameter types [OK]

Common Mistakes:

• Missing parentheses around function parameter
• Writing arrow syntax incorrectly
• Using wrong parameter types

3. What is the output of this TypeScript code?

type Fn = (x: number) => number;
function applyTwice(f: Fn, value: number): number {
  return f(f(value));
}
const double: Fn = x => x * 2;
console.log(applyTwice(double, 3));

medium

A. 12

B. 6

C. 9

D. Error

Solution

1. Step 1: Understand applyTwice function

   It applies function f twice: f(f(value)).

2. Step 2: Calculate output with double function

   double(3) = 6, then double(6) = 12, so result is 12.

3. Final Answer:

   12 -> Option A

4. Quick Check:

   applyTwice(double, 3) = 12 [OK]

Hint: Apply function twice step-by-step [OK]

Common Mistakes:

• Calculating only one application of function
• Confusing multiplication with addition
• Expecting a syntax or runtime error

4. Identify the error in this TypeScript higher-order function type declaration:

type Mapper = (fn: (x: number) => number) => number[];
const mapToArray: Mapper = fn => {
  return fn.map(x => x * 2);
};

medium

A. No error, code is correct

B. fn is a function, but .map is called on it incorrectly

C. fn parameter should be a number, not a function

D. Mapper type should return a function, not an array

Solution

1. Step 1: Check type of fn parameter

   fn is a function (x: number) => number, not an array.

2. Step 2: Analyze usage of fn.map

   Calling .map on fn is invalid because fn is not an array but a function.

3. Final Answer:

   fn is a function, but .map is called on it incorrectly -> Option B

4. Quick Check:

   Function cannot use .map method [OK]

Hint: Functions don't have .map method [OK]

Common Mistakes:

• Assuming function can use array methods
• Misreading return type
• Ignoring parameter types

5. Given this TypeScript type for a higher-order function:

type Compose = <T, U, V>(f: (b: U) => V, g: (a: T) => U) => (a: T) => V;

Which implementation correctly matches this type?

hard

A. const compose: Compose = (f, g) => a => g(f(a));

B. const compose: Compose = (f, g) => (a, b) => f(a) + g(b);

C. const compose: Compose = (f, g) => a => f(g(a));

D. const compose: Compose = (f, g) => a => f(a) * g(a);

Solution

1. Step 1: Understand Compose type

   Compose takes two functions f and g, returns a function that applies g then f.

2. Step 2: Check each implementation

   const compose: Compose = (f, g) => a => f(g(a)); applies f(g(a)) which matches the type. Others do not follow the composition pattern.

3. Final Answer:

   const compose: Compose = (f, g) => a => f(g(a)); -> Option C

4. Quick Check:

   Compose = f(g(a)) [OK]

Hint: Compose means f(g(a)) order [OK]

Common Mistakes:

• Reversing function order
• Adding parameters incorrectly
• Using arithmetic instead of function calls