# Thread: Big Oh and Big Omega

1. ## 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.

2. 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)$

3. Thanks for the reference. Greatly appreciated.

4. Incidentally, do you have any suggestions about the first problem posed ?

5. 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)$

6. 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 ?