Factorial Using Recursion in DSA Typescript - Time & Space Complexity

Time Complexity: Factorial Using Recursion

O(n)

Understanding Time Complexity

We want to understand how the time to calculate a factorial grows as the number gets bigger.

How many steps does the computer take when using recursion to find factorial?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function factorial(n: number): number {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}
    

This code calculates the factorial of a number by calling itself with smaller numbers until it reaches 1.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive call to factorial with n-1.
• How many times: Exactly n times until reaching the base case.

How Execution Grows With Input

Each time we call factorial, it does one multiplication and calls itself with a smaller number.

Input Size (n)	Approx. Operations
10	About 10 multiplications and calls
100	About 100 multiplications and calls
1000	About 1000 multiplications and calls

Pattern observation: The number of steps grows directly with n, so doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute factorial grows in a straight line as the input number gets bigger.

Common Mistake

[X] Wrong: "Recursion makes factorial calculation take much longer than looping."

[OK] Correct: Both recursion and looping here do the same number of steps, so their time grows the same way.

Interview Connect

Understanding how recursion affects time helps you explain your code clearly and shows you know how to reason about performance.

Self-Check

"What if we used a loop instead of recursion? How would the time complexity change?"