Call stack behavior in Java - Time & Space Complexity

schedule

Time Complexity: Call stack behavior

O(n)

menu_book

Understanding Time Complexity

When a program runs, it keeps track of active tasks using a call stack. Understanding how this stack grows helps us see how time grows with input.

We want to know how the number of steps changes as the program calls itself or other methods.

code_blocks

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public class StackExample {
    public static int factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(factorial(5));
    }
}
    

This code calculates the factorial of a number using recursion, where each call waits for the next.

repeat

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive call to factorial with n-1
• How many times: Once per number from n down to 1, so n times

search_insights

How Execution Grows With Input

Each time we increase n by 1, the program makes one more recursive call, adding one more step.

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

Pattern observation: The number of steps grows directly with n, increasing steadily.

cards_stack

Final Time Complexity

Time Complexity: O(n)

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

chat_error

Common Mistake

[X] Wrong: "Recursive calls happen all at once, so time is constant or very small."

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

business_center

Interview Connect

Understanding how the call stack grows with recursion helps you explain why some methods take longer and how to spot deep recursion in real problems.

psychology_alt

Self-Check

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