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

Taught in

References