How to find the time complexity of a recursive function
A working method for finding the time complexity of a recursive function: write the recurrence, draw the call tree, and check it against the master theorem. Includes worked counts for merge sort, naive Fibonacci and a slicing bug.
To find the time complexity of a recursive function, write down a recurrence: the cost of one call excluding its recursive calls, plus the cost of the calls it makes. Then solve it by drawing the call tree and summing work per level, or by applying the master theorem when the shape fits.
Most people stall on this because they try to read the answer off the code by feel. A function that calls itself twice feels exponential, and one that halves its input feels logarithmic. Both instincts are right often enough to be dangerous. Merge sort calls itself twice and is nowhere near exponential. A binary search that halves its input can still be linear. I do not trust the feel; I trust the recurrence, because it forces you to count three specific things, and every mistake I have seen comes from skipping one of them.
What is a recurrence relation and how do you write one for your code?
A recurrence is an equation that says the total cost T(n) of a call equals the work that call does by itself plus the total cost of the calls it spawns. You write it by answering three questions: how many recursive calls does one invocation make, how big is the input to each of them, and how much work happens outside those calls.
Take merge sort as the reference case.
def merge_sort(a):
if len(a) < 2: # O(1)
return a
mid = len(a) // 2
left = merge_sort(a[:mid]) # one call on n/2 items
right = merge_sort(a[mid:]) # another call on n/2 items
return merge(left, right) # O(n) to merge
Two calls, each on half the input, plus a linear merge. That gives T(n) = 2T(n/2) + n, with T(1) = 1. The slicing also costs O(n) per call, but it adds to the same linear term and changes nothing. Notice what I did not do: I did not say anything about the answer yet. Writing the recurrence is pure bookkeeping, and doing it separately from solving it is what keeps you honest. The base case matters too. It tells you where the recursion stops, which decides how deep the tree goes.
If the recurrence part feels shaky, it helps to think of the function as an inductive claim: assume the smaller calls are correct and cheap, then charge only for what this call adds. The page on recursion as induction develops that view, and the same habit makes complexity analysis much calmer.
How does the call tree method work?
The call tree method draws every call as a node, labels each node with the work it does by itself, and adds up the labels level by level. It works for any recurrence, including the ones the master theorem refuses to touch.
Here is the framing I use. Treat the tree as a payroll. Every call is an employee who does a little work personally and then hands the rest to subordinates. To get the total wage bill you do not follow individual employees around; you walk down the org chart one tier at a time and multiply headcount by salary. The only questions are how many people are in each tier and what each of them is paid. Merge sort is a company where headcount doubles every tier while salary halves, so every tier costs the same.
Do it with real numbers. Sort n = 1024 items. Level 0 has one call with 1024 items, merging costs 1024. Level 1 has two calls with 512 items each, merging costs 512 each, so 1024 again. Level k has 2^k calls of size 1024 / 2^k, and the product is always 1024. The tree reaches single-item leaves at level 10, so there are 10 merge levels, about 10 x 1024 = 10,240 element moves, plus 1024 trivial leaves. A quadratic algorithm on the same input does around 1,048,576 steps. That 100x gap is what n log n buys you, and you can see exactly where the log comes from: it is the number of tiers.
Once you have done this a few times, you notice that only three things can happen to the per-level cost as you move down the tree.
- It stays flat. Headcount grows exactly as fast as salary shrinks. Total is the per-level cost times the number of levels, as in merge sort.
- It shrinks geometrically. The top tier dominates, and the total is a constant times the root's own work.
- It grows geometrically. The bottom tier dominates, and the total is a constant times the number of leaves.
That trichotomy is the entire content of the master theorem. Everything else is notation.
When does the master theorem apply, and what does it say?
The master theorem applies when a function splits into a equal-sized subproblems of size n/b and does f(n) work outside the calls, so T(n) = aT(n/b) + f(n) with a at least 1 and b greater than 1. It tells you which of the three payroll cases you are in by comparing f(n) against n^(log_b a), which is the number of leaves.
The comparison goes like this. If the root's own work f(n) is polynomially smaller than the leaf count, the leaves dominate and T(n) is about n^(log_b a). If f(n) is about the same size as the leaf count, every level contributes equally and you get an extra log factor. If f(n) is polynomially larger, the root dominates and T(n) is about f(n) (given a mild regularity condition that holds for every ordinary function you will meet in interviews).
Run it on a few familiar cases. Binary search has a = 1, b = 2, f(n) = 1. The leaf count is n^0 = 1, which matches f(n), so the log factor appears and the answer is O(log n). Summing a balanced tree has a = 2, b = 2, f(n) = 1. The leaf count is n, much larger than 1, so leaves dominate and the answer is O(n). Merge sort has a = 2, b = 2, f(n) = n, a perfect match, so O(n log n). Quickselect on average has a = 1, b = 2, f(n) = n, and the leaf count is 1, so the root dominates: O(n). A three-way split such as Karatsuba multiplication has a = 3, b = 2, f(n) = n, leaf count n^1.585, so leaves win and the answer is O(n^1.585).
The theorem has real limits. It needs equal-sized pieces, so it says nothing about quicksort with an uneven pivot. It needs the input to shrink by a factor, so it says nothing about T(n) = T(n-1) + n. And the gap between f(n) and the leaf count has to be polynomial; n log n against n falls in a crack that needs the extended version. When any of those fail, go back to the call tree. I know people who memorise the theorem and still cannot analyse a recursive function that does not fit it. The tree never fails to apply.
| Recurrence | Typical example | Result | What dominates |
|---|---|---|---|
| T(n) = T(n/2) + O(1) | Binary search | O(log n) | Every level equal, constant each |
| T(n) = 2T(n/2) + O(1) | Sum over a balanced tree | O(n) | Leaves |
| T(n) = 2T(n/2) + O(n) | Merge sort | O(n log n) | Every level equal, n each |
| T(n) = T(n/2) + O(n) | Quickselect, average case | O(n) | Root |
| T(n) = T(n-1) + O(1) | Recursive factorial or list sum | O(n) | Depth times constant |
| T(n) = T(n-1) + O(n) | Quicksort on sorted input | O(n^2) | Arithmetic series |
| T(n) = 2T(n-1) + O(1) | Enumerating subsets with no pruning | O(2^n) | Leaves |
| T(n) = T(n-1) + T(n-2) + O(1) | Naive Fibonacci | O(1.618^n) | Leaves |
How do you analyse recursion that shrinks by one instead of halving?
When each call reduces n by a constant rather than a factor, unroll the recurrence by hand and sum the terms. The master theorem is silent here, and the tree is either a single long chain or a wide explosion, both easy to add up.
Start with T(n) = T(n-1) + n. Unrolling gives n + (n-1) + (n-2) + ... + 1, which is n(n+1)/2. For n = 1000 that is 500,500 operations, and the shape is clearly O(n^2). This is exactly what happens in quicksort when the pivot is always the smallest or largest element. On an already sorted array of 100,000 items with a naive first-element pivot, you perform roughly 5 billion comparisons. A balanced split would do about n log2 n, which is 100,000 x 16.6, about 1.66 million. Same code, same recurrence family, a 3000x difference decided entirely by how evenly the work splits.
Now T(n) = 2T(n-1) + 1. Level k has 2^k calls, each costing 1, and there are n levels, so the total is 2^n - 1. For n = 30 that is 1,073,741,823 calls. This is the shape of any function that makes two calls on an input that is only one smaller, and it is the reason naive subset or permutation enumeration is stuck at tiny n. If each of the 2^n leaves also does O(n) work to copy its result, the cost becomes n x 2^n; permutations similarly cost n x n!. Remember the leaf work, because it multiplies.
Naive Fibonacci is the instructive middle case. T(n) = T(n-1) + T(n-2) + 1 is not exactly 2^n, because the second branch is smaller. The tree is lopsided: the left spine is n deep, the right spine is about n/2 deep. The true growth rate is the golden ratio, about 1.618^n. For fib(30), the call count satisfies C(n) = C(n-1) + C(n-2) + 1, which works out to 2 x F(31) - 1 = 2,692,537 calls. The bound 1.618^30 is about 1.86 million, the same order of magnitude once you allow the constant. Saying O(2^n) is a valid upper bound, and I would accept it in an interview, but knowing it is a bit loose is the kind of detail that shows you did the arithmetic rather than recited it.
Does memoisation change the time complexity of a recursive function?
Yes, and often dramatically. With memoisation, the cost becomes the number of distinct states multiplied by the work done per state, because each state is computed once and every later request is a lookup.
Go back to fib(30). Without a cache it makes 2,692,537 calls. With a cache, only 31 distinct inputs exist (0 through 30). Each of the 29 non-base states makes two child calls, so there are 58 child calls plus the root, 59 calls in total, and 29 of those are cache hits. The recurrence did not get smarter; the tree got pruned so that every repeated subtree collapses into a single leaf. The complexity drops from exponential to O(n).
The rule generalises well beyond Fibonacci. For coin change with amount A and k coin values, the state is the remaining amount, so there are at most A + 1 states, and each tries k coins. That gives O(A x k), versus a tree that can branch k ways to depth A. You can try it on Coin Change and count the states yourself. The one trap is a state that is too rich. If your memo key includes a whole list or a mutable set, the number of distinct states may be exponential anyway, and the cache gives you memory cost with no time savings. The honest question is always: how many different argument tuples can this function actually be called with? Whether you then fill the table top-down or bottom-up is a separate choice, covered in memoisation versus tabulation.
What mistakes do people make when analysing recursive complexity?
The common mistakes are ignoring the non-recursive work in each call, assuming splits are balanced, confusing depth with total cost, and counting calls instead of work. Each one gives an answer that looks plausible and is wrong.
The first is the one I see most often, and it hides in innocent-looking Python. Consider this binary search.
def contains(a, x):
if not a:
return False
mid = len(a) // 2
if a[mid] == x:
return True
if a[mid] < x:
return contains(a[mid + 1:], x) # slice copies the right half
return contains(a[:mid], x) # slice copies the left half
There is one recursive call on half the input, so the instinct says T(n) = T(n/2) + 1 and O(log n). But each slice copies about n/2 elements, so the real recurrence is T(n) = T(n/2) + n/2. The root dominates, and the total is n/2 + n/4 + n/8 + ... which is about n. For a million elements, a proper index-based search does about 20 comparisons; this version copies roughly a million elements in total. It is linear, not logarithmic, and the code looks identical to a textbook binary search. Whenever you write the recurrence, ask what the non-recursive part really costs, including slicing, string building, list concatenation and anything hidden inside a library call.
The second mistake is assuming the split is even. Quicksort, tree recursion on unbalanced trees, and divide and conquer on skewed data can all degrade, and the right move is to state the best, average and worst recurrences separately. A binary tree traversal is O(n) regardless of shape, since each node is visited once, but a recursion that depends on the tree's height will be O(n) per call on a linked-list-shaped tree and O(log n) on a balanced one.
The third is conflating depth with cost. A recursion of depth n is not automatically O(n) time. The naive Fibonacci tree has depth n and takes exponential time, because the number of nodes matters, not just the length of one path. Depth does determine space, though: the call stack holds one frame per level of the current path, so recursion depth n costs O(n) stack. In CPython the default limit is about 1000 frames, which is why a recursion that is fine at n = 500 can crash at n = 5000. How much that overhead matters in practice is a separate question, and is recursion slower than iteration deals with it directly.
The fourth is counting calls when work per call varies. A function that makes n calls is not O(n) if each call does a loop over the input. Always multiply, and when the per-call cost changes with depth, sum it level by level. This is the same discipline behind treating complexity as a promise about specific operations, an idea I develop in complexity is a contract, not a fact.
What is a reliable routine to use every time?
Use the same five steps on every function: define n, write the recurrence from the code, draw two or three levels of the tree with real numbers, decide which of the three payroll cases applies, and then state the space from the depth of the deepest path.
- Pick what n means. For an array it is the length, for a tree it is the node count, for a number it may be the value itself, which matters because an O(n) loop over a value is exponential in its bit length.
- Write the recurrence with three numbers: calls, subproblem size, outside work.
- Plug in a small concrete n, such as 16 or 1024, and count work on the first three levels. Do not skip this; patterns appear in numbers faster than in symbols.
- If it fits aT(n/b) + f(n), use the master theorem as a check on what the tree told you. If it does not, sum the tree directly.
- Ask whether any state repeats. If yes, count distinct states and multiply by the per-state work for the memoised cost.
I would argue the tree matters more than the theorem. In interviews, nobody expects you to cite case 2. They expect you to say that there are log n levels and each level does n work, and to defend it when pushed. If you can do that with a concrete n on the whiteboard, you have already given the interviewer the answer they are listening for.
Frequently asked questions
Do I need to memorise the master theorem for interviews?
Not formally. Know the three outcomes in plain language: leaves dominate, every level is equal, or the root dominates. If you can draw the tree for merge sort and explain why it is n log n, you can handle nearly every divide and conquer question you will be asked.
How do I find the space complexity of a recursive function?
Take the depth of the deepest chain of active calls and multiply by the space each frame holds, then add any structures the function allocates and keeps alive. Merge sort uses O(log n) stack but O(n) for merge buffers, so the total is O(n). A naive memoised Fibonacci uses O(n) for both the stack and the cache.
Why does my recursive function have the same complexity as the loop version?
Because complexity counts operations, and a loop and a recursion that perform the same operations cost the same asymptotically. The recursion adds constant overhead per call and uses stack space proportional to its depth, which can matter in practice but does not change the Big O of the time.
The next step is to apply the routine to something with a cache: write the recurrence, count the distinct states, and check that your count matches the cost of your memoised solution on Coin Change