🌳 Recursion Tree Calculator
Enter a divide-and-conquer recurrence and an input size to expand its recursion tree level by level — see how many subproblems each level holds, how big they are, how much work they do, and what it all sums to.
🧩 Expand T(n) = a·T(n/b) + nᵈ
🌳 Recursion tree — 4 levels, total work 32
| Level | Subproblems (aᴸ) | Size (n/bᴸ) | Work this level |
|---|---|---|---|
| 0 | 1 | 8 | 8 |
| 1 | 2 | 4 | 8 |
| 2 | 4 | 2 | 8 |
| 3 | 8 | 1 | 8 |
| Total work | 32 | ||
The tree bottoms out after log_b(n) = 3 recursion steps (level 0 is the original call).
What is a Recursion Tree Calculator?
It unrolls a recurrence into the tree of recursive calls it generates and does the bookkeeping for you. For your chosen a, b, d, and n it computes, for each level, the number of subproblems (a raised to the level), their size (n divided by b to the level), and the total work that level performs — then sums every level to give the algorithm's running time.
Seeing the per-level work laid out in a table makes it obvious whether the cost is dominated by the root, the leaves, or spread evenly — the exact distinction the Master Theorem formalises. It is a great companion for checking a Master Theorem answer by hand and for building a mental picture of how divide-and-conquer algorithms spend their time.
❓ Frequently Asked Questions
What is the recursion tree method?
The recursion tree method visualises a recurrence by drawing the recursive calls as a tree: the root is the original problem, and each node branches into its subproblems. You compute the work done at each level, sum across all levels, and that total is the algorithm's running time. It is the intuition the Master Theorem packages into a formula.
How is the work at each level computed?
At level L there are a^L subproblems, each of size n/b^L, and each does (n/b^L)^d work for f(n) = n^d. So the work at level L is a^L · (n/b^L)^d. This tool tabulates the subproblem count, subproblem size, and per-level work for every level, then adds them up for the total.
How many levels does the tree have?
The recursion bottoms out when the subproblem size reaches 1, which happens after log_b(n) halvings — so there are floor(log_b n) levels below the root, and this tool counts level 0 (the original call) through that bottom level.
How does this relate to the Master Theorem?
The recursion tree is where the three Master Theorem cases come from. When work grows toward the leaves you get Case 1, when it is equal across levels you get the extra log n factor of Case 2, and when it is concentrated at the root you get Case 3. Reading the per-level column here shows you which pattern your recurrence follows.