How can I find the asymptotic behavior of a sum like \(\sum_{i = 1}^{\lfloor \log_2 (n) \rfloor} \sqrt{i}\)?
Note 1: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Classic
GUID:
modified
Note Type: Horvath Classic
GUID:
lg2TVeS_j]
Before
Front
Back
How can I find the asymptotic behavior of a sum like \(\sum_{i = 1}^{\lfloor \log_2 (n) \rfloor} \sqrt{i}\)?
Sum and integral have the same asymptotic behavior (not covered in lecture)!
\[\begin{align} \sum_{i=1}^{\lceil \sqrt{n} \rceil} \sqrt{i} &\sim \int_1^{\lceil \sqrt{n} \rceil} \sqrt{x}\,dx \\ &= \left[\frac{2}{3}x^{3/2}\right]_1^{\lceil \sqrt{n} \rceil} \\ &= \frac{2}{3}\bigl(\lceil \sqrt{n} \rceil^{3/2} - 1\bigr) \\ &\sim \frac{2}{3}\bigl(n^{1/2}\bigr)^{3/2} \\ &= \Theta(n^{3/4}). \end{align}\]
(We use \(\sim\) to denote asympotic equivalence. Correct but verbose would be to wrap everything in \(\Theta\))
\[\begin{align} \sum_{i=1}^{\lceil \sqrt{n} \rceil} \sqrt{i} &\sim \int_1^{\lceil \sqrt{n} \rceil} \sqrt{x}\,dx \\ &= \left[\frac{2}{3}x^{3/2}\right]_1^{\lceil \sqrt{n} \rceil} \\ &= \frac{2}{3}\bigl(\lceil \sqrt{n} \rceil^{3/2} - 1\bigr) \\ &\sim \frac{2}{3}\bigl(n^{1/2}\bigr)^{3/2} \\ &= \Theta(n^{3/4}). \end{align}\]
(We use \(\sim\) to denote asympotic equivalence. Correct but verbose would be to wrap everything in \(\Theta\))
After
Front
How can I find the asymptotic behavior of a sum like \(\sum_{i = 1}^{^{\lceil \sqrt{n} \rceil}} \sqrt{i}\)?
Back
How can I find the asymptotic behavior of a sum like \(\sum_{i = 1}^{^{\lceil \sqrt{n} \rceil}} \sqrt{i}\)?
Sum and integral have the same asymptotic behavior (not covered in lecture)!
\[\begin{align} \sum_{i=1}^{\lceil \sqrt{n} \rceil} \sqrt{i} &\sim \int_1^{\lceil \sqrt{n} \rceil} \sqrt{x}\,dx \\ &= \left[\frac{2}{3}x^{3/2}\right]_1^{\lceil \sqrt{n} \rceil} \\ &= \frac{2}{3}\bigl(\lceil \sqrt{n} \rceil^{3/2} - 1\bigr) \\ &\sim \frac{2}{3}\bigl(n^{1/2}\bigr)^{3/2} \\ &= \Theta(n^{3/4}). \end{align}\]
(We use \(\sim\) to denote asympotic equivalence. Correct but verbose would be to wrap everything in \(\Theta\))
\[\begin{align} \sum_{i=1}^{\lceil \sqrt{n} \rceil} \sqrt{i} &\sim \int_1^{\lceil \sqrt{n} \rceil} \sqrt{x}\,dx \\ &= \left[\frac{2}{3}x^{3/2}\right]_1^{\lceil \sqrt{n} \rceil} \\ &= \frac{2}{3}\bigl(\lceil \sqrt{n} \rceil^{3/2} - 1\bigr) \\ &\sim \frac{2}{3}\bigl(n^{1/2}\bigr)^{3/2} \\ &= \Theta(n^{3/4}). \end{align}\]
(We use \(\sim\) to denote asympotic equivalence. Correct but verbose would be to wrap everything in \(\Theta\))
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | How can I find the asymptotic behavior of a sum like \(\sum_{i = 1}^{ |
How can I find the asymptotic behavior of a sum like \(\sum_{i = 1}^{^{\lceil \sqrt{n} \rceil}} \sqrt{i}\)? |