# Big Oh and Big Omega

• May 1st 2008, 07:49 PM
Ian Moore
Big Oh and Big Omega
Here is a problem I'm having trouble with:

Find big Oh and big Omega of log(n!)

I have tried Stirling's formula but I'm not sure that this is a satisfactory approach.

Any suggestions/help would be appreciated.

The other problem is to solve the recurrence relation

T(n) = 3T(n/4)+n

I simply cannot see the approach required here to solve this.
Again any help would be appreciated.
• May 2nd 2008, 03:23 AM
Isomorphism
Quote:

Originally Posted by Ian Moore
The other problem is to solve the recurrence relation

T(n) = 3T(n/4)+n

I simply cannot see the approach required here to solve this.
Again any help would be appreciated.

Master theorem - Wikipedia, the free encyclopedia is a wonderful tool. You should learn it up.

The answer using masters theorem would be $\displaystyle O(n)$
• May 3rd 2008, 08:51 PM
Ian Moore
Thanks for the reference. Greatly appreciated.
• May 3rd 2008, 08:54 PM
Ian Moore
Incidentally, do you have any suggestions about the first problem posed ?
• May 3rd 2008, 10:02 PM
Isomorphism
Quote:

Originally Posted by Ian Moore
Here is a problem I'm having trouble with:

Find big Oh and big Omega of log(n!)

I have tried Stirling's formula but I'm not sure that this is a satisfactory approach.

It is a valid approach.

Alternatively observe that:

$\displaystyle [\forall i \in \mathbb{N}: 2 < i <n] , \log 2 < \log i < \log n$

This implies $\displaystyle \log(n!) \in O(n\log n)$ and $\displaystyle \log(n!) \in \Omega(n)$
• May 4th 2008, 12:01 AM
Ian Moore
Thankyou for your reply on Big O and Big Omega of log(n!).
You say that log(n!) is an element of Big Omega of n.

I would have thought that it is the same as Big Oh, i.e.
log(n!) = O(nlog(n)) and log(n!) = Omega(nlog(n))

Surely this is a consequence of Stirlings formula ?