Math Is Fun Forum

NumOne

Member

Registered: 2012-01-16

Posts: 9

Prove of Asymptotic Notation

Hi

I need to prove the following statements:

1) for any a>1, and any b, a^n ∈ ω(n^b).

We have to prove f(n) > C.g(n) for all C>0, n0>0 and n>=n0
a^n > C . n^b

Since a > 1 , I think a >= n and a > b
which assures that the left hand side will be always greater than the right hand side.

Is that right ?

2) We have f(n)= n^2 and g(n)=42.
Is f(n) ∈ O (g(n)) or f(n) ∈ Ω(g(n)) ?

What I think is f(n) ∈ Ω(g(n))
n^2 >= C.g(n)
n must be >= 7 and C = 1
Is this prove right or not ?

Thanks