1
$\begingroup$

I guess I've already figured out what is a recursion tree and how to construct one. Inspired by Figure 2.5 of "Introduction to Algorithms, 3rd Edition by CLRS", I drew some recursion trees for the recurrence $T(n) = 2T(n/2) + cn$.

the recursion tree for the recurrence when n=16

enter image description here

the recursion tree for the recurrence when n=13

enter image description here

the recursion tree for the recurrence when n=7

enter image description here

Could someone help double-check my understanding?

$\endgroup$

1 Answer 1

3
$\begingroup$

$T(n/2)$ is not well-defined if $n$ is odd. The merge sort recurrence - if you want to take floors and ceilings into account - is actually $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + cn$. So, if $n=13$, the subproblems would have sizes $7$ and $6$, respectively (not $8$ and $5$, respectively).

It’s ok to be sloppy and assume $n$ is a power of $2$ because that doesn’t affect the final conclusions. Recursion trees are usually drawn with this simplifying assumption, and the intuition carries over to the general case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.