recursion tree
A picture of a recursive algorithm's calls as a tree, with the work done at each call written beside it, used to total the cost.
In more detail
Summing each level and multiplying by the number of levels often gives the answer directly. For merge sort there are log n levels each costing n. For naive Fibonacci the tree roughly doubles at each level, which shows its exponential cost.
Related terms
- recurrence relation — An equation that defines an algorithm's cost on input size n in terms of its cost on smaller inputs, such as T(n) = 2T(n/2) + n.
- recursion — A technique where a function solves a problem by calling itself on a smaller version of the same problem.
Taught in
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers