Tuesday, 6 January 2015

asymptotics - Summation with Floor and Square Root functions + Tight Bounds



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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...