f(n)=log n! ,g(n)=n logn what is the relationship between them?

Question

Comments

How to calculate the lower bound for these functions?

Answer 1

https://www.youtube.com/watch?v=gS4Z-fBiOU4

also search for stirling approximaiton

Comments

n=theta (n/2)

then why not 2^n=theta 2^(n/2).

I know !n<=nlogn

But how can we prove !n<=nlogn please explain.I don't want to prove using strilling approximation

---

n=theta (n/2)

then why not 2^n=theta 2^(n/2).

What rule you applied here, I mean how can you take an exponential and still expect result to hold? The first statement is not an "equality" and this is clearly mentioned in asymptotic notation - see Cormen and not some notes. Theta notation just means the growth rate of LHS is same as that of the RHS or the function on LHS belongs to the set of functions whose growth rate is same as that on the RHS. It is not an equality such that we can substitute LHS for RHS at other places. 

I know !n<=nlogn

who told this is true? This is just false and hence can't be proved. n! is just the multiplication of all natural numbers from 1 to n. On RHS we just multiply n with log n. 

---

Sorry arjun sir,

I actually wanted to write log n!<=nlogn

I can prove like this

Log n!=log1+log2+........logn

(If I replace these terms by higher terms)

           <=logn+logn+.......logn

        <=nlogn

so I can say that log n!=O(nlogn)

And the reason I say 2^n=theta 2^n/2 bcz if we take log both sides

Then nlog2=theta n/2log2(if we assume base2)

       n=theta n/2