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:
added
Note Type: Horvath Classic
GUID:
lg2TVeS_j]
Previous
Note did not exist
New Note
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\))
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | How can I find the asymptotic behavior of a sum like \(\sum_{i = 1}^{\lfloor \log_2 (n) \rfloor} \sqrt{i}\)? | |
| Back | Sum and integral have the same asymptotic behavior (not covered in lecture)!<br><br>\[\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}\]<br> (We use \(\sim\) to denote asympotic equivalence. Correct but verbose would be to wrap everything in \(\Theta\)) |
Note 2: ETH::A&D
Deck: ETH::A&D
Note Type: Horvath Classic
GUID:
added
Note Type: Horvath Classic
GUID:
m{e.+pS,Zn
Previous
Note did not exist
New Note
Front
How can you find the upper bound of a geometric series like \(T = 7^1, 7^2, \ldots, 7^n\)?
Back
How can you find the upper bound of a geometric series like \(T = 7^1, 7^2, \ldots, 7^n\)?
Use the multiply-subract trick.
- Mutliply the series by its base: \(7T\)
- Subtract: \(7T - T = 7^{n+1} - 7^1\) (middle terms cancel)
- Factor: \(T(7-1) = 7^{n+1} - 7^1\)
- Divide: \(T = \frac{7^{n+1} - 7^1}{6}\)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | How can you find the upper bound of a geometric series like \(T = 7^1, 7^2, \ldots, 7^n\)? | |
| Back | Use the multiply-subract trick.<br><ol><li>Mutliply the series by its base: \(7T\)</li><li>Subtract: \(7T - T = 7^{n+1} - 7^1\) (middle terms cancel)</li><li>Factor: \(T(7-1) = 7^{n+1} - 7^1\)</li><li>Divide: \(T = \frac{7^{n+1} - 7^1}{6}\)</li></ol> |