0
$\begingroup$

i want to prove upper bound of the following recurrence $ T(n) =T(n-\sqrt{n})+1 $ is $ O(\sqrt{n})$.

$\endgroup$
2
  • $\begingroup$ What have you tried? $\endgroup$
    – integrator
    Nov 1, 2020 at 16:03
  • 1
    $\begingroup$ Proving this formally is more involved than it might first seem. $\endgroup$ Nov 1, 2020 at 20:46

1 Answer 1

1
$\begingroup$

Define a sequence by $n_0 = n$, $n_{i+1} = n_i - \sqrt{n_i}$. Let $\ell$ be the maximal index such that $n_\ell \geq n/2$. For $i \leq \ell$ we have $\sqrt{n_i} \geq \sqrt{n/2}$, and so $n/2 \leq n_\ell \leq n - \ell \sqrt{n/2}$. It follows that $\ell \leq \sqrt{n/2}$.

Let $\ell_t$ be the maximal index such that $n_{\ell_t} \geq n/2^t$; so $\ell_0 = 0$ and $\ell_1 = \ell$. The preceding paragraph shows that $\ell_{t+1} - \ell_t \leq \sqrt{n_{\ell_t}/2}$. Since $n_{\ell_t+1} < n/2^t$, it follows that $n_{\ell_t} - \sqrt{n_{\ell_t}} < n/2^t$. If $t \leq \log_2 n$ then $n_{\ell_t} \geq 1$, and so $(\sqrt{n_{\ell_t}}-1)^2 = n_{\ell_t} - 2\sqrt{n_{\ell_t}} + 1 \leq n_{\ell_t} - \sqrt{n_{\ell_t}} < n/2^t$, and so $\sqrt{n_{\ell_t}} < \sqrt{n/2^t} + 1$. Therefore if $n_{\ell_t} \geq 1$ then $\ell_{t+1} - \ell_t \leq \sqrt{n/2^{t+1}} + 1/2$. It follows that if $t \leq \log_2 n$ then $$ \ell_{t+1} \leq \sqrt{n/2} + \cdots + \sqrt{n/2^{t+1}} + t/2 = O(\sqrt{n} + t). $$ Choosing $t = \lfloor \log_2 n \rfloor$, we get that the maximal index $s$ such that $n_s \geq 1$ is at most $\ell_{t+1} = O(\sqrt{n} + \log n) = O(\sqrt{n})$.

This shows that assuming an initial condition of the form $T(n) = O(1)$ for $n \leq 1$, you can bound $T(n) = O(\sqrt{n})$; a matching lower bound is obvious (at each step, the value of the parameter decreases by at most $\sqrt{n}$).

Using similar ideas, you can show that if you replace $\sqrt{n}$ by its floor or ceiling, then the resulting recurrence still grows like $\Theta(\sqrt{n})$.

What is the constant factor in the asymptotics of $T(n)$? If we define $\tau(s) = n_s$ and think of $\tau$ as continuous, then $\tau' = -\sqrt{\tau}$, and so $\tau(s) = (c-s)^2/4$. Since $\tau(0) = n$, we find that $c = 2\sqrt{n}$, and so $\tau(s) = (2\sqrt{n}-s)^2/4$. Therefore $\tau(s) = 0$ for $s = 2\sqrt{n}$, and so we expect $T(n) \sim 2\sqrt{n}$. This is indeed borne out by experiments, which suggest that $T(n) = 2\sqrt{n} - \Theta(\log n)$.

$\endgroup$

Your Answer

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