1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ The height of your recurrence tree is roughly $\max(\log_2n,\log_4k)$. Your recurrence for $H$ should have a $\max$ instead of a $+$. $\endgroup$ – Yuval Filmus Nov 5 '20 at 9:10
  • $\begingroup$ 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 $\endgroup$ – user128010 Nov 5 '20 at 10:02
1
$\begingroup$

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.

Equivalently, the height of a tree is the maximum length of a root-to-leaf path (in edges; if you measure it in vertices, leaves should have height 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.

$\endgroup$
1
  • $\begingroup$ $H(n,k) = \max(H(\tfrac{n}{2},k), H(n,\tfrac{k}{4})) + 1$ is not correct. $\endgroup$ – user132812 Mar 17 at 15:05

Your Answer

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