views:

87

answers:

1

I have 3 functions: f(n)=2n, g(n)=n! and h(n)=nlog(n) (log(n) is base 2).

Comparing f(n) and g(n): The factorial function, g(n) can be approximated as O(nn) (poor upper bound). Considering this, Is g(n)=Ω(f(n)) ?

How would I compare g(n) and h(n), and f(n) and h(n)?

+1  A: 

(Shallow answers for homework)

Use Stirling's approximation for factorial function to study it's asymptotic.

For second question, If you have difficulties studying functions as they're given, try to study logarithms of them. Then infer the relationship between given functions based on the results you've obtained for logarithms (these results won't be equivalent!)

Pavel Shved