0
$\begingroup$

I know if the time complexity of an algorithm is given with the above formula, then the algorithm works in constant time but my question is that what will be the height of the recursion tree for this formula?

$\endgroup$
  • $\begingroup$ @"AK 12" If you meant, for example, $T(n)=T(n-\sqrt n) + 1$ or $T(n)=T(\lfloor n-\sqrt n\rfloor) + 1$, please update your post. $\endgroup$ – Apass.Jack Jun 11 at 12:22
  • $\begingroup$ @Apass.Jack Sorry for the mistake. I edited the post and replaced "linear" with constant. My question is that how many steps does it take to reach T(0) ? $\endgroup$ – AK 12 Jun 12 at 12:41
3
$\begingroup$

If you are asking how many iterations of the function $x\mapsto x-\sqrt x$ does it take to get from $n$ below $1$:

For a lower bound, the resulting sequence is nonincreasing, hence you remove at most $\sqrt n$ at each step, hence you need at least $$\frac n{\sqrt n}=\sqrt n$$ steps.

For an upper bound: in order to get from $n$ to $n/2$, all the steps will remove at least $\sqrt{n/2}$, hence $$\frac{n/2}{\sqrt{n/2}}=\sqrt{n/2}$$ steps are enough for that. By the same argument, $\sqrt{n/4}$ steps are enough to get from $n/2$ to $n/4$, $\sqrt{n/8}$ from $n/4$ to $n/8$, etc. The total number of steps is bounded by the geometric series $$\sqrt n\left(\sqrt{1/2}+\sqrt{1/4}+\sqrt{1/8}+\cdots\right)=\sqrt n\frac{\sqrt{1/2}}{1-\sqrt{1/2}}=\frac{\sqrt n}{\sqrt 2-1}\approx2{.}4\sqrt n.$$

Thus, the required number of steps is $\Theta(\sqrt n)$; a more precise argument would show that it is $\bigl(2+o(1)\bigr)\sqrt n$.

$\endgroup$
  • $\begingroup$ Special thanks! Exactly what I needed. $\endgroup$ – AK 12 Jun 13 at 16:19
3
$\begingroup$

Clearly T(n) = T(0) for all n. Which is constant, not linear. Is that really the question you wanted to ask?

And I just see a mathematical relation. I can’t see any recursion or tree or algorithm here.

$\endgroup$
  • $\begingroup$ Sorry for the mistake. I edited the post and replaced "linear" with constant. My question is that how many steps does it take to reach T(0) ? $\endgroup$ – AK 12 Jun 12 at 9:04
  • $\begingroup$ The recursion tree of the function int f(int n) { if (n=1) return 1; else return f(n-sqrt(n)); } (or whatever base case is actually intended). $\endgroup$ – David Richerby Jun 12 at 16:04

Your Answer

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

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