CS Algorithm question

[The_OG_Nelta]

well let's say i have f(n) = n(2^n) and g(n) = 3^n,
3^n obviously grows faster, but how should i prove this? let's say i wanna prove f(n) = O(g(n))
any hint?

[Cheerios]

9

[Devek]

I introduce to you.. basic math.

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Math/

[Tubbers]

Master's Theorem. If that doesn't work, MAKE it work.

[Viena]

http://en.wikipedia.org/wiki/Mathematical_induction

[Zigma]

well let's say i have f(n) = n(2^n) and g(n) = 3^n,
3^n obviously grows faster, but how should i prove this? let's say i wanna prove f(n) = O(g(n))
any hint?

D1(n) = T(n)-T(n-1) = a*n2+b*n+c-a*(n-1)2-b*(n-1)-c = 2a*n-a+b

DUH!

[Cat]

Take the largest growth item from both sides, since it will be the only significant growth factor as n goes to inifinty.
Thus f(n) = 2? and g(n) = 3?.
Thus f(n) = O(g(n)).

[Maguspk]

Knowing certain things work that way and proving it are two different things.

If you all tried to pull that shit on a Calculus test you'd get points taken off, unless your teacher was an idiot.

My calculus is rusty but try the root test with 2^n and 3^n. Should be easy enough...

Edit: If you haven't had Calc2 yet that would explain why you're finding this difficult, in which case I feel bad because that would really suck

[Charla]

Take the ratio of g(n) to f(n) as n approaches infinity.

In this case that would be (3^n)/(n(2^n)) = ((3/2)^n)/n.
Now if the limit of ((3/2)^n)/n as n approaches infinity is greater than 1, then g(n) grows faster, if it's less than 1, then f(n) grows faster, and if it's 1 then they grow at the same rate. I don't remember how to resolve that limit, but you're the one taking the class so you should be able to figure it out better than me.

[Cheerios]

Fucking alphabet math.