I'm studying algorithm analysis by "Introduction to alogrithm".

What I'm learning is proof by recursion tree but I can't understand how can I calculate height of recursion tree.

So I searched stackoverflow and found the answer but there was no details.

How to determine the height of a recursion tree from a recurrence relation?

Can you explain why $\log_b n$ can be depth(height)?

  • $\begingroup$ How many times can you divide $n$ by $b$ before reaching $1?$. $\endgroup$ Commented Mar 11, 2018 at 23:34
  • $\begingroup$ That's what I want to know. How I compute that? $\endgroup$
    – haram
    Commented Mar 11, 2018 at 23:39
  • $\begingroup$ @haram, Hint: With $b$ fixed, you need to solve $b^k\leq n\lt b^{k+1}$ for $k$ (this is the height of the tree, or more explicitly, the height is $\lfloor k\rfloor$ or $\lceil k\rceil$ depending upon convention/context). $\endgroup$ Commented Mar 11, 2018 at 23:42
  • $\begingroup$ @PrasunBiswas In your explanation, n is the number of all nodes of recursion tree? $\endgroup$
    – haram
    Commented Mar 11, 2018 at 23:47
  • $\begingroup$ Yes, it's the same $n$ you're talking about and $b$ is for the number of recursive calls at each node (similar to what happens in a $b$-ary tree) $\endgroup$ Commented Mar 11, 2018 at 23:52


You must log in to answer this question.

Browse other questions tagged .