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.
Thanks in advance.
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.
Originally Posted by Ian Moore
The answer using masters theorem would be
Thanks for the reference. Greatly appreciated.
Incidentally, do you have any suggestions about the first problem posed ?
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 ?