# How do you find the height of the recurrence tree $T(n,k)=T(\frac{n}{2},k)+T(n,\frac{k}{4})+nk$

I try to find tree height such that first i define: $$H(n,k)=H(\frac{n}{2},k)+H(n,\frac{k}{4})+1$$ then find height of left branch of tree=logn & right branch of tree=logk,but now why height of tree is equal to logk+logn?i guess height of tree is Max(logn,logk)why my geuss is not true?

• The height of your recurrence tree is roughly $\max(\log_2n,\log_4k)$. Your recurrence for $H$ should have a $\max$ instead of a $+$. – Yuval Filmus Nov 5 '20 at 9:10
• please if you can explain why my argument(my guess) is true?in solution manual used + instead of max but i say it's not true – user128010 Nov 5 '20 at 10:02

Here is a recursive definition of a height of a tree $$T$$:
• If $$T$$ is a leaf, then its height is 0 (some people prefer to use 1).
• Otherwise, the height of $$T$$ is the maximum height of any of its children, plus 1.
This makes it clear that the correct recurrence for the height is $$H(n,k) = \max(H(\tfrac{n}{2},k), H(n,\tfrac{k}{4})) + 1,$$ with an appropriate base case. The solution is roughly $$\max(\log_2 n, \log_4 k)$$, depending on the base case.
• $H(n,k) = \max(H(\tfrac{n}{2},k), H(n,\tfrac{k}{4})) + 1$ is not correct. – user132812 Mar 17 at 15:05