Call stack behavior - Time & Space Complexity

Time Complexity: Call stack behavior

O(n)

Understanding Time Complexity

When a program runs functions, it uses a call stack to keep track of where it is. Understanding how this stack grows helps us see how time and work increase.

We want to know how the number of function calls affects the total work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void countdown(int n) {
    if (n == 0) return;
    countdown(n - 1);
}

int main() {
    countdown(5);
    return 0;
}
    

This code calls a function that calls itself repeatedly, counting down from n to 0.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive function calls to countdown.
• How many times: The function calls itself n times before stopping.

How Execution Grows With Input

Each time we increase n by 1, the function calls itself one more time, adding one more step.

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

Pattern observation: The work grows directly with n, like climbing stairs one step at a time.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the input size n.

Common Mistake

[X] Wrong: "Recursive calls happen all at once, so time stays the same no matter n."

[OK] Correct: Each call waits for the next one to finish, so calls add up one after another, increasing total time.

Interview Connect

Understanding how the call stack grows with recursion helps you explain why some functions take longer as input grows. This skill shows you can think about program behavior clearly.

Self-Check

"What if the countdown function called itself twice each time? How would the time complexity change?"