# How do I find an upper bound on this recurrence

$f(n)=f(n-\sqrt{n})$

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?

• 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$. – D.W. Sep 14 '15 at 16:27
• 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. – 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})$.
• Can you explain why the decrease at every step being at least $\sqrt{n/2}$ gives us the $\leq$ ? That piece is confusing me – shane Sep 14 '15 at 18:27
• 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. – Yuval Filmus Sep 14 '15 at 18:33