I have an algorithm that at each step can discard $\lceil\sqrt(n)\rceil$ possibilities at a cost $1$. The solution to the recurrence relation below is related to the question of complexity of such algorithm:

$$T(n) = T\left(n-\lceil\sqrt n\rceil\right) + 1$$

I know that: $T(0)=0$, $T(1) = 1$.

I tried substituting $n=2^{2^k}$ but it did not get me far.

  • 1
    $\begingroup$ I guess you want to see a proof that $T(n)\sim2\sqrt{n}$. But first, what is the meaning of the recursion $T(n)=T(n-\sqrt{n})+1$? What is the definition set of $T$ (since $n-\sqrt{n}$ is often not an integer)? $\endgroup$ – Did Apr 2 '14 at 20:58
  • $\begingroup$ I suppose $T(0)=0$ is the starting point of the recursion, since, as it is now stated, you'll get $T(2)=T(0)+1$. $\endgroup$ – Einar Rødland Apr 3 '14 at 6:20
  • $\begingroup$ Did's answer that $T(n) = \Theta(\sqrt{n})$ is correct (with an overhead constant of about 2 as he said); it can be proven using induction on the definition of theta runtime, whether $n$ is an integer or not and what the starting value is doesn't affect the runtime. This question should not have been locked. $\endgroup$ – DanielV Apr 3 '14 at 6:45
  • $\begingroup$ FWIW, the sequence $T(n)=0,1,1,2,2,2,3,3,3,4,\ldots$ appears to be related to oeis.org/A154287 -- i.e., the first $n$ for which $T(n)=k$ seems to agree with $a(k)=1,3,6,9,13,\ldots$. $\endgroup$ – Barry Cipra Apr 3 '14 at 22:27

As did has already pointed out, $T(n)\sim2\sqrt{n}$. Any easy way to arrive at this conclusion is to pretend $T(n)$ is defined for all real numbers and continuous, and approximate $$ 1=T(n)-T(n-\lceil\sqrt{n}\rceil)\approx\sqrt{n}T'(n) $$ for large $n$, which makes $T'(n)\approx1/\sqrt{n}$ and in turn, by integration, $T(n)\approx2\sqrt{n}$.

Computing $T(n)$ using Maple, indeed reveals that $$ T(n)=2\sqrt{n}-\frac{\ln(2\sqrt{n}+1)}{\ln2}+\epsilon_n $$ where $\epsilon_n\in[-0.1,1]$.

A more formal proof of $T(n)\sim2\sqrt{n}$ is possible, but a bit more technical.

Let's write $n'=n-\lceil\sqrt{n}\rceil$. Then, $$ \left(\sqrt{n}-\tfrac{1}{2}\right)^2-\tfrac{5}{4}\le n-\sqrt{n}-1\le n' \le n-\sqrt{n}=\left(\sqrt{n}-\tfrac{1}{2}\right)^2-\tfrac{1}{4}. $$

First, assume $T(k)\le2\sqrt{k}$ for $k<n$: this holds for $k<1$, which starts the induction. Then, using $n'<(\sqrt{n}-1/2)^2$, $$ T(n)=T(n')+1\le2\sqrt{n'}+1\le 2\left(\sqrt{n}-\tfrac{1}{2}\right)+1=2\sqrt{n}. $$

Next, assume $T(n)\ge2\sqrt{n}-\tau(n)$ for some function $\tau(n)$. Using $$ 2\sqrt{n'} \ge \sqrt{(2\sqrt{n}-1)^2-5} \ge 2\sqrt{n}-1-\frac{5}{2\sqrt{n}-1}, $$ this makes $$ T(n)=T(n')+1\ge 2\sqrt{n'}+1-\tau(n') \ge 2\sqrt{n}-\frac{5}{2\sqrt{n}-1}-\tau(n'), $$ and so $T(n)\ge 2\sqrt{n}-\tau(n)$ holds if we define $\tau(0)=0$ and $$ \tau(n)=\tau(n')+\frac{5}{2\sqrt{n}-1}. $$ In turn, we now have $$ \frac{\tau(n)-\tau(n')}{n-n'} =\frac{5}{(2\sqrt{n}-1)\cdot\lceil\sqrt{n}\rceil} \le\frac{5}{(2\sqrt{n}-1)\cdot\sqrt{n}} <\frac{5+\delta}{2n} $$ for any $\delta>0$ and sufficiently large $n$. From this follows that $\tau(n)$ at worst is $O(\ln n)$.

| cite | improve this answer | |
  • $\begingroup$ +1. Nice way of dealing with the lower bound. I like the way you do not decide beforehand what the error term will be but let the proof decide, so to speak. $\endgroup$ – Did Apr 3 '14 at 23:07
  • $\begingroup$ I really like the solution. It thought me different approach to difference relation. And it put me on right track how to prove the algorithm, that started the problem, is optimal and of complexity $2\sqrt(n)$. $\endgroup$ – Tahtisilma Apr 4 '14 at 5:33

Here is a geometric intuition. We started with a width of $\sqrt{n}$. At each step, the width reduced by (1/2). Hence within roughly $2\sqrt{n}$ steps we reach the base case.

| cite | improve this answer | |

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.