Summation with floor in upper bound

Question

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.

Answer 1

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). $$