Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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
the recursion tree for the recurrence when n=13
the recursion tree for the recurrence when n=7
Could someone help double-check my understanding?
$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.
