Timeline for Find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 13, 2017 at 19:10 | comment | added | Yos | Let us continue this discussion in chat. | |
| Jul 13, 2017 at 18:52 | comment | added | ryan | It's just the sum of 1 to $\log m$. Check here. The main idea is that $\sum_1^n i = \Theta(n^2)$ for any $n$. | |
| Jul 13, 2017 at 18:48 | comment | added | Yos | One last question: is there a formula for $\sum_{i=1}^{\log m} i$? I didn't find anything on google so far | |
| Jul 13, 2017 at 18:39 | comment | added | Yos | Yes, I understood that in the end after you get $\sqrt n=2^{2^{k-1}}$ then because $k=\log \log n$ we "unroll" $2^{2^{k-1}}$ by $\log{\log{2^{2^{k-1}}}}$ | |
| Jul 13, 2017 at 18:36 | comment | added | ryan | The point of $R$ is to represent just how $k$ changes in the recurrence $T$. $R$ is different than $T$, but if we get a bound on $R$ we can infer a bound on $T$. Establishing $T(\sqrt{n}) = T(2^{2^{k-1}})$ would leave us in the same place we started just in a different form. $R$ abstracts the difficulties of $T$ by only dealing with the variable $k$ rather than $2^{2^k}$. | |
| Jul 13, 2017 at 18:25 | comment | added | ryan | I kinda hid the assumption that $n = 2^{2^k}$ and also hid the assumption that log bases were 2 but that's typically assumed. So we then have $\sqrt{2^{2^k}} = 2^{2^{k-1}}$. Check here for more info. | |
| Jul 13, 2017 at 18:17 | comment | added | Yos | And regarding your second method why if $k=\log{\log n}$ then $\sqrt n=k-1$? | |
| Jul 13, 2017 at 18:06 | comment | added | ryan | I've made one edit expanding the step you mention. The problem in your comment is $\dots \neq m \cdot \log m - \dots$, it should be $ = \log m \cdot \log m - \dots$, because the expansion will only continue as many steps as we can divide $m$ by $2$, which would be $\log m$. | |
| Jul 13, 2017 at 18:04 | history | edited | ryan | CC BY-SA 3.0 |
Added extra detail
|
| Jul 13, 2017 at 17:53 | comment | added | Yos | if $m=\log n$: let $m=2^k$ then as far as I understand the development is $\log m+\log{m \over 2}+\log{m \over 4}+...+\log{m \over k}=\log m+\log m -\log 2+ \log m -\log 4+...+\log m-\log k=m\cdot \log m-\sum_{i=1}^{2^k}\log 2^i=m\cdot \log m-\frac{\log m(\log m +1)}{2}=m\cdot \log m-{1 \over 2}(\log^m+\log m)=\Theta \log ^m$. Is this correct? | |
| Jul 13, 2017 at 17:30 | history | answered | ryan | CC BY-SA 3.0 |