Timeline for why is $O(t(n)b^{t(n)}) = 2^{O(t(n))}$
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 19, 2013 at 4:38 | comment | added | CodeKingPlusPlus | @LukeMathieson Thanks for not giving me all of the answer. Let me know what you think of my revision. | |
| Nov 19, 2013 at 4:36 | history | edited | CodeKingPlusPlus | CC BY-SA 3.0 |
content revision
|
| Nov 18, 2013 at 3:39 | comment | added | Luke Mathieson | @CodeKingPlusPlus there's a way you can rewrite any expression to be $2^{something}$. A simple one might be if you have a number $x$, then there's some $y$ such that $x = 2^{y}$, even better, there's a way, if you "know" $x$, to get $y$ - you can do the same thing with a function etc. | |
| Nov 17, 2013 at 7:41 | comment | added | CodeKingPlusPlus | Could you leave another hint? I'm not so sure how $t(n)$ can be expressed as a power of $2$. | |
| Nov 17, 2013 at 4:02 | comment | added | Luke Mathieson | You might want to deal with the multiplicative $t(n)$ (kind-of) separately: can you express $t(n)$ as power of two? (It's not so different from what you've already shown) | |
| Nov 17, 2013 at 3:16 | comment | added | CodeKingPlusPlus | Yes, I agree with you. I was thinking of that $t(n)$ as being a coefficient. Oops. I'll look over it again tomorrow. | |
| Nov 17, 2013 at 1:20 | comment | added | G. Bach | I miss a proof that we can always choose $c$ such that $c\cdot t(n) \le 2^{c\cdot t(n)}$. | |
| Nov 17, 2013 at 0:44 | history | answered | CodeKingPlusPlus | CC BY-SA 3.0 |