2
$\begingroup$

What is the asymptotic rate of growth of the following recurrence?

$$ T(n) = n + T(n - \sqrt{n}). $$

Since I cannot use the Master's Theorem here, I could not figure it out the answer. My initial guess is $n^{3/2}$, but I'm not sure.

Can anyone help me? What are the big-O and big-Omega complexities here?

$\endgroup$
1
  • $\begingroup$ If we assume that you mean $T(n)=n + T(n - \sqrt{n})$, it's easy to see, that rough estimation gives $O(n)$, so less, then you expected. $\endgroup$
    – zkutch
    Apr 26 at 23:10
3
$\begingroup$

You can get a lower bound of $\Omega(n^{3/2})$ as follows. Consider the number of steps it takes to get from $n$ to $n/2$. Since at each step, $n$ decreases by at most $\sqrt{n}$, this takes at least $\sqrt{n}/2$ steps. At each such step, we accumulate at least $n/2$, for a total of at least $n^{3/2}/4$.

You can prove a matching upper bound using a similar approach. While the input parameter is at least $n/2$, it decreases by at least $\sqrt{n/2}$, and so it takes at most $\sqrt{n/2}$ steps to get to $n/2$. During each such step, we accumulate at most $n$, for a total of at most $n^{3/2}/\sqrt{2}$. An identical argument shows that at most $(n/2)^{3/2}/\sqrt{2}$ is accumulated while going from $n/2$ to $n/4$, and so on. Hence $$ T(n) \leq \frac{n^{3/2}}{\sqrt{2}} \left(1 + \frac{1}{2^{3/2}} + \frac{1}{4^{3/2}} + \cdots\right) = O(n^{3/2}), $$ since the geometric series inside the parentheses converges.

Numerical experiments suggest that $$ T(n) \sim \frac{2}{3} n^{3/2}. $$ We can show this heuristically as follows. Let us imagine that $T$ is a recurrence in continuous time. Then $T(n) - T(n-\sqrt{n}) \approx \sqrt{n} T'(n)$, and so $$ T'(n) \approx \sqrt{n}. $$ Integrating, we get $$ T(n) \approx \frac{n^{3/2}}{3/2} = \frac{2}{3} n^{3/2}. $$ This can probably be showed by running the argument above more carefully (replacing $n/2$ with $(1-\epsilon)n$).

$\endgroup$

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.