Generate All Permutations of Array in DSA Typescript - Time & Space Complexity

Time Complexity: Generate All Permutations of Array

O(n × n!)

Understanding Time Complexity

When we generate all permutations of an array, we want to know how the time needed grows as the array gets bigger.

We ask: How does the number of steps change when the input size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function permute(nums: number[]): number[][] {
  const result: number[][] = [];
  function backtrack(start: number) {
    if (start === nums.length) {
      result.push([...nums]);
      return;
    }
    for (let i = start; i < nums.length; i++) {
      [nums[start], nums[i]] = [nums[i], nums[start]];
      backtrack(start + 1);
      [nums[start], nums[i]] = [nums[i], nums[start]];
    }
  }
  backtrack(0);
  return result;
}
    

This code generates all possible orderings (permutations) of the input array by swapping elements and exploring all options recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls combined with a loop that swaps elements to create permutations.
• How many times: The recursion explores every possible ordering, which is factorial in number of elements (n!).

How Execution Grows With Input

Each time we add one more element, the number of permutations multiplies by that new number.

Input Size (n)	Approx. Operations
3	6 (3 x 2 x 1)
5	120 (5 x 4 x 3 x 2 x 1)
7	5,040 (7 x 6 x 5 x 4 x 3 x 2 x 1)

Pattern observation: The number of operations grows very fast, multiplying by the input size each time.

Final Time Complexity

Time Complexity: O(n × n!)

This means the time needed grows very fast because we explore every possible order of the array elements, and each permutation takes linear time to copy.

Common Mistake

[X] Wrong: "Generating permutations is just like looping through the array once, so it should be O(n)."

[OK] Correct: Each element can be in many positions, creating many combinations. The total grows factorially, not linearly.

Interview Connect

Understanding this complexity helps you explain why some problems take longer and shows you can reason about recursive solutions clearly.

Self-Check

"What if we only generated permutations of half the array? How would the time complexity change?"