Stavros and Jessica are discussing about runtime of an algorithm which is given by the following recurrence relation:

T$($m$)=$ T$($m$)+$ T$(2$m$)+$ c$2$m$,$ T$(1)=$ d$.33$

Stavros: I think T$($m$)$ in O$($mlogm$).$ Let$$s use recursion tree method to show this. The longest path from the root to a leaf is log$3$ m$.$ after drawing the tree we can see the cost of

$2$

each level $($including the last one$)$ is less than or equal to c$2$m$.$ So$,$ the total cost is c$2$mlog$3$ m in O$($mlogm$).$

$2$

$1$

$2.$

$3.$

Jessica: I believe T $($m$)$ in $\backslash$omega $($m log m$).$ Actually based on your argument, T $($m$)$ is exponen$-$

tial in terms of m$.$ I agree with the upper bound on the height of the recursion tree which is log$3$ m

log$3$ m$.$ However, using the fact that the tree may have $22$ leaves $($based on its height$)2$

and the cost of a leaf being the constant d$,$ we can see that the cost of leaves is exponential in m$.$ That is why T$($m$)$ is in $\backslash$omega $($mlogm$)$ and this implies that T$($m$)$ cannot be in O$($mlogm$).$

Explain in details, what is correct and what is wrong in the above discussion. More precisely, provide details on which part of their argument is correct and which part is not. Moreover, provide a tight bound for T$($m$)$ and justify your answer only for the upper bound.