Timeline for How to the examples for using the master theorem in Cormen work?
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
|
|
| Feb 12, 2013 at 6:21 | vote | accept | Vahagn Babajanyan | ||
| Feb 12, 2013 at 6:21 | |||||
| Feb 2, 2013 at 23:27 | comment | added | Vahagn Babajanyan | Cormen says. The asymptotic upper bound provided by O-notation may or may not be asymptotically tight. The bound $2n^{2} = O(n^{2})$ is asymptotically tight, but the bound $2n = O(n^{2})$ is not. We use o-notation to denote an upper bound that is not asymptotically tight. That is infinity lim. I thought that Big O and Omega should be always asymptoticaly tight, so lim should not be equal to infinity, and only now i understand what he means. Thanks a lot. You help me to understand it. | |
| Feb 2, 2013 at 21:24 | comment | added | Raphael | Yes, you are mistaken. $\omega(f) \subseteq \Omega(f)$. I don't get what you mean by "tight bound", and what "it" refers to. | |
| Feb 2, 2013 at 20:45 | comment | added | Vahagn Babajanyan | I mean how can we proove that it is tight bound? | |
| Feb 2, 2013 at 20:18 | comment | added | Vahagn Babajanyan | I mean for $\Omega$, $\lim_{n \to \infty} \frac{n \log n}{n^{\alpha}} \neq \infty$. Because for $\omega$ it should be infinity, but for $\Omega$ it shouldn't, or i'm mistaken? | |
| Feb 2, 2013 at 20:12 | comment | added | Raphael | @VahagnBabajanyan: It's a corollary from $n \log n \in \omega(n)$, using only the definitions of $\omega$ and $\Omega$ as well as the (almost trivial) fact that $n^\alpha \in o(n^\beta)$ for all $\alpha < \beta$. | |
| Feb 2, 2013 at 19:56 | comment | added | Vahagn Babajanyan | Thanks for the answer. I understand all except how you get $n \log n \in \Omega(n^\alpha)$ equation. If it is possible could you explain it? | |
| Feb 2, 2013 at 13:44 | history | answered | Raphael | CC BY-SA 3.0 |