big Oh, omega and theta functions

[Piffo]

Hey guys,

 

I came accross this proof while I was studying this material but I am have a hard time with it. Does anybody know how to go about showing those too equivalencies??

 

Prove that log(n!) = Theta(n log n) by proving the following two claims:

• log(n!) = O(n log n).

• log(n!) = *omega(n log n).

 

Thanks!!

[Aeternus]

For [math]\log(n!) = O(n \log n)[/math] consider that,

 

[math]

\log(n!) = \log(\prod_{i=1}^{n}{i})

[/math]

 

which given [math]\log(a*b) = \log(a) + \log(b)[/math] is

 

[math]

\log(n!) = \sum_{i=1}^{n}{\log(i)}

[/math]

 

Now remember that, log is monotonic, it preserves order, ie we have [math] \forall\,x,y \in \mathbb{R} : x > y \Rightarrow \log(x) > \log(y) [/math], meaning we know [math]\log(n) > \log(n-1)[/math] so we have

 

[math]

\sum_{i=1}^{n}{\log(n)} \ge \sum_{i=1}^{n}{\log(i)}

[/math]

 

So

 

[math]

n\log(n) \ge log(n!) \,\forall \, n \ge 0

[/math]

[Piffo]

Hey man,

 

thanks a bunch, I got that part.

 

Any idea how to go about the second section of the proof?.

[Aeternus]

You might want to look into Stirling's approximation and the bounds on the error there (the error is guaranteed to be within a certain bound dependent on n). Using some log rules, and choosing a decent enough constant for the [math]\Omega[/math] condition should make it all work out nicely.