Time complexity

[esti]

Hi,

 

I'm struggling with these 2 questions:

 

 

I'm trying to understand what should i prove here and what is the approach for solving that?

 

Q1: both expressions are O(nlogn) ?

Q2: ??

 

 

Tnx,

Shimon

 

 

 

[mathematic]

First one is easy ∑ log(k) (k=1,n) compared to nlog(n). Obviously nlog(n) is bigger.

 

Second is a little confusing, Left term exponent. What is it the exponent of: argument of ln or ln of argument?

[esti]

 

Second is a little confusing, Left term exponent. What is it the exponent of: argument of ln or ln of argument?

 

Yep, I am also confused with that - need to check

[AtomicMaster]

my natural logs are rusty, but if i recall:

 

[math]ln(e^{e^k})=e^k[/math]

[math]ln(e^k)=k[/math]

[math]ln\left( e^{e^k}\right)^k=ln(e^{e^k*k})=e^k*k[/math]

 

so second relationship should therefore be:

[math]e^k*k, e^{e^k*k}[/math]

 

(feel free to check all that though)

[Enthalpy]

http://en.wikipedia.org/wiki/Stirling%27s_approximation

Log(fact(N)) ~ N*Log(N) -N +0.5*Log(2pi*N)