- #1
Klion
- 14
- 0
Alright problem is pretty simple, I have two functions
f(x) = n!
g(x) = 2^n
Question is to show that g(x) = Of(x) through mathematical expression
that is show the growth rate of g(x) <= that of f(x)
The fact that this is true is fairly obvious, it's bigger for n>3.
Anyway my problem is I only know how to define n! as a recursive definition, so I'm not really sure how to demonstrate this truth in any kind of mathematical way. If you put both as a reiman product or whatever it's called (ie n-i for i=0 to n and 2 for i=0 to n) you have a function compared to a number.
like
2*2*2*2*...*2 (n terms)
1*2*...*(n-1)*(n) (n terms)
I don't really want to use induction since I don't think it's necessary or expected, and I don't really know how to do the inductive step since one of the functions has no variables.
Anyway any ideas? Or anyone know a non recursive definition for factorial so I can compare it to 2^n? heh
f(x) = n!
g(x) = 2^n
Question is to show that g(x) = Of(x) through mathematical expression
that is show the growth rate of g(x) <= that of f(x)
The fact that this is true is fairly obvious, it's bigger for n>3.
Anyway my problem is I only know how to define n! as a recursive definition, so I'm not really sure how to demonstrate this truth in any kind of mathematical way. If you put both as a reiman product or whatever it's called (ie n-i for i=0 to n and 2 for i=0 to n) you have a function compared to a number.
like
2*2*2*2*...*2 (n terms)
1*2*...*(n-1)*(n) (n terms)
I don't really want to use induction since I don't think it's necessary or expected, and I don't really know how to do the inductive step since one of the functions has no variables.
Anyway any ideas? Or anyone know a non recursive definition for factorial so I can compare it to 2^n? heh