Analyzing the Time Complexity of Recursive Functions
Demystify the complexity of recursion by learning how to trace function calls, base cases, and execution branching.
The Invisible Loops
Calculating Big O for loops is easy because you can see them. Calculating Big O for recursion is notoriously difficult because the repetition is hidden within the Call Stack.
To analyze recursive time complexity, you must answer two questions:
- How many times does the function call itself?
- How much work is done inside each call?
Single Branch Recursion: O(N)
Look at a simple recursive countdown:
void count(int n) {
if (n == 0) return; // Base Case
print(n); // O(1) work
count(n - 1); // Single recursive call
}
If N is 5, the function calls itself for 4, 3, 2, 1, 0. That is 5 total calls. Inside each call, it does O(1) work (printing). Total time = (Number of calls) * (Work per call) = N * 1 = O(N) Linear Time.
Halving Recursion: O(log N)
What if the recursive step halves the data, like in Binary Search?
void search(int n) {
if (n <= 1) return;
search(n / 2); // Halving the input
}
If N is 16, it calls 8, 4, 2, 1. It only makes 4 calls. Because the input divides by 2 on every step, it requires O(log N) Logarithmic Time.
The Takeaway
Not all recursion is slow, and not all recursion is fast. The time complexity of a recursive algorithm is entirely dependent on how the input size N is manipulated as it is passed into the next recursive call.
You determine the total number of times the function is recursively called (the nodes in the recursion tree) and multiply it by the amount of non-recursive work done in each call.
If it decrements by 1 (e.g., n-1) and makes a single call, it forms a straight line of N calls, resulting in O(N) Linear Time.
Because instead of decrementing by 1, it divides the input size by 2 on each recursive call, slashing the required number of calls logarithmically.
Traversing an entire tree to visit every node is O(N) because you must process all N nodes. Searching a perfectly balanced Binary Search Tree is O(log N).
Yes, the base case defines when the recursion stops. If the base case is poorly designed, it can cause the recursion to run infinitely, leading to a Stack Overflow.