2
$\begingroup$

While solving Recurrences of type $T\left ( n \right ) = a\cdot T(\frac{n}{b})+c$ using the recursion tree method, number of levels in the recursion tree is equal to $\log_{b}n$ when $b$ is a constant.
But when $b$ is dependent on $n$, can we say that number of levels are still $\log_{b}n$?
For example, in
$T\left ( n \right ) = a\cdot T\left ( \frac{n}{\sqrt{n}} \right )+c$

Can we say that number of levels in the recursion tree are equal to $\log_{\sqrt{n}}n = 2$?
I guess this is wrong but I am unable to reason it properly, please explain me the reason "why this is wrong?"(If it really is).

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ I think our reference question has methods for such parameters of $T$. See also here. $\endgroup$
    – Raphael
    Commented Jan 19, 2016 at 8:27

1 Answer 1

Reset to default
1
$\begingroup$

If $b$ is not a constant, then no, you can't say the number of levels is still $\log_b n$.

In your example, we have $T(n) = a T(\sqrt{n}) + c$ (since $n/\sqrt{n} = \sqrt{n}$). There are more than 2 levels in the recursion tree. In fact, there are $\lg \lg n$ levels in the recursion tree. So, no, you can't just compute $\lg_{\sqrt{n}} n = 2$ and conclude that there are 2 levels in the recursion tree -- that gives the wrong answer.

(Why $\lg n$? Suppose $n=2^k$. Then each level halves $k$, so we do a total of $\lg k$ levels we get down to a constant. Since $k = \lg n$, we get a total of $\lg k = \lg \lg n$ levels.)

The Master theorem gives a formula for solving this kind of recurrence, but it's only valid when $b$ is a constant.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I understood what you said but actually I wrote $T\left ( n \right ) = a\cdot T\left ( \sqrt{n} \right ) + c$ itself as $T\left ( n \right ) = a\cdot T\left ( \frac{n}{\sqrt{n}} \right )+c$ to see that by what fraction of $n$ the problem is getting reduced with each level of the tree, so that I can easily compute number of levels by using logarithm.I don't think taking $\sqrt{n}$ as log base should be an issue as $\log_{\sqrt{n}}n= \frac{\log_{2}n}{\log_{2}{\sqrt{n}}}$.Could you please tell me what went wrong here, why my estimation for number of levels is wrong? $\endgroup$
    – Romy
    Commented Jan 19, 2016 at 9:02
  • $\begingroup$ @Romy, it's because your line of reasoning is only valid when $b$ is a constant. If you're still confused, I suggest you try writing down a careful justification for why your line of reasoning should be valid, and then you might discover at what step it goes awry; if not, edit the question with that detailed reasoning to give us something concrete to respond to. $\endgroup$
    – D.W. ♦
    Commented Jan 19, 2016 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.