# Why the height of recursion tree is $\log_b n$?

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)?

• How many times can you divide $n$ by $b$ before reaching $1?$. Commented Mar 11, 2018 at 23:34
• That's what I want to know. How I compute that? Commented Mar 11, 2018 at 23:39
• @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). Commented Mar 11, 2018 at 23:42
• @PrasunBiswas In your explanation, n is the number of all nodes of recursion tree? Commented Mar 11, 2018 at 23:47
• 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) Commented Mar 11, 2018 at 23:52