Timeline for Papadimitrou and standard landau notation
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 10, 2014 at 11:38 | vote | accept | Rudimentary Joe | ||
| Dec 10, 2014 at 9:48 | comment | added | Gilles 'SO- stop being evil' | @RudimentaryJoe $g(n) \le 1$ was a typo, it should have been $g(n) \ge 1$. Having a positive minimum for $g$ is what makes the proof work. It doesn't have to be $1$, the proof would work (with a different $c$) as long as there exists an $\epsilon \gt 0$ such that $\forall n \ge n_0, g(n) \ge \epsilon$. | |
| Dec 10, 2014 at 9:47 | history | edited | Gilles 'SO- stop being evil' | CC BY-SA 3.0 |
fixed typo (thanks Rudimentary Joe)
|
| Dec 10, 2014 at 2:53 | comment | added | Rudimentary Joe | In your second proof there is $f(n) \leq (c'+d'/g(n))g(n) \leq (c'+d')g(n)$. It holds true for $g(n)=1$ But considering $g(n)<1$ wouldn't it be the other way around? $(c'+\frac{d'}{g(n)})g(n)\geq(c'+d')g(n)$ as $\frac{d'}{g(n)}>d'$? And also why did you put the $g(n)\leq 1$? | |
| Dec 10, 2014 at 1:39 | history | answered | Gilles 'SO- stop being evil' | CC BY-SA 3.0 |