Factorial Using Recursion in DSA C - Time & Space Complexity

Time Complexity: Factorial Using Recursion

O(n)

Understanding Time Complexity

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

Specifically, how many steps does the recursive factorial function take as input increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}
    

This code calculates the factorial of a number using recursion by multiplying n with factorial of n-1 until it reaches 0.

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 base case n=0 is reached

How Execution Grows With Input

Each increase in input n adds one more recursive call, so the steps grow directly with n.

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

Pattern observation: The number of steps grows in a straight line as n increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute factorial grows directly in proportion to the input number.

Common Mistake

[X] Wrong: "Recursion makes factorial calculation take exponential time because it calls itself many times."

[OK] Correct: Each recursive call happens only once per number down to zero, so calls grow linearly, not exponentially.

Interview Connect

Understanding how recursion affects time helps you explain and optimize solutions clearly in interviews.

Self-Check

"What if we changed the recursion to use a loop instead? How would the time complexity change?"