Draw a recursion tree for this recurrence:

The tree should look like:

It should show at least 4 levels of the tree. In addition to the tree itself, you need to include appropriate cost expressions over on the right, as shown in these examples. Unlike the given examples, your tree should bottom out with T(2) as the label of each leaf, rather than T(1), because thats the base case of the recurrence above. Also, the height of your tree will be log2n rather than1 + log2n, as shown in the examples. The purpose of this problem is to gain some familiarity with recursion trees. Focus on showing the correct branching structure of the tree, correct node labels, and correct cost labels.

T(n) {er(0/2+ do if n = 2, if n > 2. 2T(n/2) + dn2 Ex 3. If T(n) satisfies T(n)= 3 T (n/4) + n, with T(1)= 1, then T(n) = (n). Tn) n5 T(1/4) Tm/4) T(m4) 3 (n/4) / / Tn/ 16) Tn/ 16) Tn/ 16) Tn/16) Tn/ 16) (1/16) Tn/16) Tn/ 16) Tn/ 16) 32 (n/42,5 1 + log4n 3' (n/44)5 : : T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) ... T(1) T(1) T(1) zlog, " (n/4logan)5 zloga n = nlog, 3 p=3 / 4%