Time Complexity: Stack memory
O(n)
0
0
Stack memory in Java - Time & Space Complexity
Understanding Time Complexity
Let's explore how the time cost grows when using stack memory in Java programs.
We want to see how the program's steps increase as we add more function calls or data on the stack.
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, which uses stack memory for each call.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Recursive calls to factorial function.
- How many times: The function calls itself n times until it reaches the base case.
How Execution Grows With Input
Each increase in input size adds one more function call on the stack.
| Input Size (n) | Approx. Operations |
|---|---|
| 5 | 5 calls |
| 10 | 10 calls |
| 100 | 100 calls |
Pattern observation: The number of steps grows directly with the input size.
Final Time Complexity
Time Complexity: O(n)
This means the time to complete grows in a straight line as the input number increases.
Common Mistake
[X] Wrong: "Recursion always makes the program slow and complex."
[OK] Correct: Recursion can be simple and efficient for problems like factorial, where each call does a small, clear step.
Interview Connect
Understanding how stack memory affects time helps you explain recursion clearly and shows you know how function calls impact performance.
Self-Check
"What if we changed the recursion to a loop? How would the time complexity change?"