Skip to interview prep
Apexed

59. How does the recursion-tree method work, and what does it give for T(n) = T(n/3) + T(2n/3) + n?

MediumAlgorithm analysis

Technical
Show model answer

Draw each call as a node labelled with the non-recursive work it does, expand level by level, sum the work per level and then sum across levels. It is a good way to guess a bound that you can then confirm with the substitution method.

For T(n) = T(n/3) + T(2n/3) + n, each full level sums to n because the sub-problem sizes add up to the parent size. The shortest root-to-leaf path has length log_3 n and the longest has length log_(3/2) n, so the total is between about n log_3 n and n log_(3/2) n, which is Θ(n log n). The master theorem does not apply directly because the split is uneven.

How does the recursion-tree method work, and what does it give for T(n) = T(n/3) + T(2n/3) + n — Data structures & algorithms interview question — Apexed