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.

  • $\begingroup$ Please give the algorithm in pseudocode. $\endgroup$ – 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). $$


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.