1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Please give the algorithm in pseudocode. $\endgroup$
    – Raphael
    Apr 12, 2017 at 19:15

1 Answer 1

3
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.