Thread: Big O notation.Show using the definition of O(f)?

Hi I'm having some trouble with big O notation. I know how to do the simple ones but this is above my head. Any help would be appreciated.

Show using only the definition of O(f) that:
1) 5^n is O(n!)
2)n! is not O(5^n)

I know that 5^n<=n! for n=12 but I don't know how to show this. The book says to use induction 'but I don't know how and for 2 as well. Any ideas?

Thanks in advance.

1) 5^n is O(n!)

Intuitive idea: in , all factors are equal to 5, whereas in , the factors start with 1 but soon overtake 5 and continue to increase. So, , but this won't last long. Calculate and for n=6,7,...,12. As you said, is already less than 12!. This can be established by direct calculation (e.g., in Windows' calculator).

Now what happens when we move from to for ? is multiplied by 5 to get ; but is multiplied by to get . So, it is clear that implies for .