0
$\begingroup$

I was applying a methodology that allows to come up with iterative algorithms time-complexity function's closed-form.

I ran into a particular where I ended up with the result below.

I wouldn't have deduced the final result without wolfram alpha.

What are the steps to following to solve the summation?

Since the closed-form contains floor and square root function, how to determine a tight order of growth bounds ($\Theta(x)$)?

$$ \\ \sum_{i=1}^{\left \lfloor \frac{n}{\left \lfloor \sqrt n \right \rfloor} \right \rfloor} (i \left \lfloor \sqrt n \right \rfloor )^3 = \frac{1}{4}\left \lfloor \sqrt n \right \rfloor ^3 \left \lfloor \frac{n}{\left \lfloor \sqrt n \right \rfloor} \right \rfloor ^2 \left ( \left \lfloor \frac{n}{\left \lfloor \sqrt n \right \rfloor} \right \rfloor + 1 \right)^2 $$

$\endgroup$
1
$\begingroup$

The $\lfloor \sqrt{n} \rfloor$ factor in the summation is constant, so we can pull it out of the sum. Then we get $\lfloor \sqrt{n} \rfloor^3 \sum_{i=1}^k i^3$, where $k = \left\lfloor \frac{n}{\lfloor \sqrt{n} \rfloor} \right\rfloor$. This is then a sum of cubes, for which there is the formula $\sum_{i=1}^k i^3 = \frac{1}{4} k^2 (k+1)^2$.

As for the asymptotics, note that $\sqrt{n} - 1 < \lfloor \sqrt{n} \rfloor \le \sqrt{n}$. This means $\lfloor \sqrt{n} \rfloor \sim \sqrt{n}$ as $n \rightarrow \infty$. Since you only have constant powers in the expression, you only need to make this estimate finitely many times, and hence the errors cannot accumulate. Thus you may treat $\lfloor \sqrt{n} \rfloor$ as $\sqrt{n}$ to determine the asymptotics.

$\endgroup$

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.