I believe $f(n)\in O(\sqrt{n})$

However I cannot seem to prove it, my intuition comes from the fact that we can remove $\sqrt{n}$ exactly $\sqrt{n}$ times, but if $n$ shrinks then does anything change?

  • $\begingroup$ 1. Try proving it. Have you tried using proof by induction to prove that your conjecture is true? You can also look at our reference question on this topic -- see especially the guess & prove answer. 2. Are you sure you have your recurrence correct? It's not $f(n) = f(n-\sqrt{n}) + 1$ or something like that? As it stands a solution to your recurrence is $f(n)=1$ for all $n$. $\endgroup$ – D.W. Sep 14 '15 at 16:27
  • $\begingroup$ In fact, $f$ could be any constant function, but you're still not out of the woods yet. Assuming the domain of the function is the non-negative reals, we'll eventually have $f(n)=f(t)$ for some $t<0$ and then in the next recurrence we'll need to take the square root of a negative number and we're skunked. $\endgroup$ – Rick Decker Sep 14 '15 at 16:42

For definiteness, let's assume that the recurrence is $$ f(n) = \begin{cases} f(\lfloor n-\sqrt{n} \rfloor) + 1 & n > 0 \\ 0 & n = 0. \end{cases} $$ (We assume that the domain is the non-negative integers.)

Since $\lfloor n-\sqrt{n} \rfloor > n-\sqrt{n}-1$, we see that $$ f(n) \geq \frac{n}{\sqrt{n}+1} = \Omega(\sqrt{n}). $$ In the other direction, let us note that $f(n)$ is monotone and that $$ f(n) \leq f(\lfloor n/2 \rfloor) + \frac{\lceil n/2 \rceil}{\sqrt{\lceil n/2 \rceil}}. $$ This is because until the parameter gets down to $\lfloor n/2 \rfloor$ (or smaller), the decrease at every step is at least $\sqrt{\lceil n/2 \rceil}$. This shows that $$ f(n) \leq f(\lfloor n/2 \rfloor) + \sqrt{\lceil n/2 \rceil} \leq f(\lfloor n/2 \rfloor) + \sqrt{n/2} + 1. $$ Iterating this $\log_2 n+1$ times, we get $$ \begin{align*} f(n) &\leq f(\lfloor n/2 \rfloor) + \sqrt{n/2} + 1 \\ &\leq f(\lfloor n/4 \rfloor) + \sqrt{n/2} + \sqrt{n/4} + 2 \\ &\leq \cdots \\ &\leq f(0) + \sqrt{n/2} + \sqrt{n/4} + \cdots + \sqrt{n/2^{\log_2 n + 1}} + \log_2n + 1 \\ &\leq \sqrt{n} \sum_{t=1}^\infty \frac{1}{\sqrt{2}^t} + O(\log n) \\ &= O(\sqrt{n}). \end{align*} $$ We conclude that $f(n) = \Theta(\sqrt{n})$.

| cite | improve this answer | |
  • $\begingroup$ Can you explain why the decrease at every step being at least $\sqrt{n/2}$ gives us the $\leq$ ? That piece is confusing me $\endgroup$ – shane Sep 14 '15 at 18:27
  • $\begingroup$ I'm using the fact that $f$ is monotone, which I haven't proved but seems true. Beyond that, I encourage you to keep thinking and see if it starts making sense. $\endgroup$ – Yuval Filmus Sep 14 '15 at 18:33

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.