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
$$
Answer
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.
No comments:
Post a Comment