# Summation with floor in upper bound

I'm learning about asymptotics and time complexity.
The algorithm I'm analyzing has a for loop that starts at $i = 1$ and ends at $\left \lfloor \sqrt n \right \rfloor$. The body is said to run in $n-i$ steps. I'm trying to do a summation from $i=1$ to $\left \lfloor \sqrt n \right \rfloor$ to come up with a Big Theta, but I am not sure how to deal with the upper bound of the summation. Thank you in advance.

• Please give the algorithm in pseudocode. – Raphael Apr 12 '17 at 19:15

You want to estimate $$S := \sum_{i=1}^{\lfloor \sqrt{n} \rfloor} (n-i).$$ You can start with the formula $$S(m) := \sum_{i=1}^m (n-i) = m \left(n - \frac{m+1}{2}\right).$$ The formula for $S(m)$ is an increasing function for $m \leq n-1/2$ (as you can check by computing the derivative), and so $\sqrt{n} - 1 < \lfloor \sqrt{n} \rfloor \leq \sqrt{n}$ implies (for $n \geq 2$) that $$S(\sqrt{n}-1) < S \leq S(\sqrt{n}+1).$$ Substituting, we get $$n^{3/2} - \frac{3}{2}n + \frac{\sqrt{n}}{2} < S \leq n^{3/2} - \frac{n}{2} - \frac{\sqrt{n}}{2}.$$ Therefore $S = n^{3/2} - O(n)$. In particular, $S = \Theta(n^{3/2})$.
We can also get an exact formula: $$S := \lfloor \sqrt{n} \rfloor \left(n - \frac{\lfloor \sqrt{n} \rfloor + 1}{2}\right).$$