# Time complexity Help

• Nov 16th 2013, 02:51 PM
zevelBen
Time complexity Help
Hi,

I'm struggling with these 2 questions:
Attachment 29747

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,
• Nov 16th 2013, 05:24 PM
emakarov
Re: Time complexity Help
Quote:

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

In a), you should say whether the following statements hold: log(n!) = O(nlog(n)), nlog(n) = O(log(n!)) and similarly with Θ and Ω replacing O.

Quote:

Originally Posted by zevelBen
Q1: both expressions are O(nlogn) ?

Yes, but you can not only bound both functions from above by nlog(n), you can also bound log(n!) from below by nlog(n), i.e., log(n!) = Θ(nlog(n)). This means that all six statements hold for these two functions.

Showing log(n!) ≤ nlog(n) is easy using properties of log. For log(n!) = Ω(nlog(n)) use a bound related to Stirling's approximation: $n!\ge n^ne^{-n}\sqrt{2\pi n}$.

For b), simplify both sides using the fact that ln(x) and e^x are mutually inverse.
• Nov 17th 2013, 07:35 PM
johng
Re: Time complexity Help
Hi,
I assume you know calculus. The following are very often useful:
Let $f(n)$ and $g(n)$ be non-negative functions. Assume
$\lim_{n\rightarrow\infty}{f(n)\over g(n)}=L$

1. If $L\neq0$ then $f(n)=\Theta(g(n))$ and so also $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$.

2. If L=0, then $f(n)=O(g(n))$, but $f(n)\neq\Omega(g(n))$ (and so $f(n)\neq\Theta(g(n))$

Both 1) and 2) are easy consequences of the definition of limit and the orders.

Example:
Recall $\int \text{ln}(x)\,dx=x\text{ln}(x)-x$ and so $\int_1^n \text{ln}(x)\,dx=n\text{ln}(n)-n+1$
By approximating Riemann sums and the fact that ln is increasing,

$\sum_{k=1}^{n-1}\text{ln}(k)\leq\int_1^n \text{ln}(x)\,dx\leq\sum_{k=2}^{n}\text{ln}(k)$

With a little more argument, you can see that

$\lim_{n\rightarrow\infty}{\sum_{k=1}^{n}\text{ln}( k)\over n\text{ln}(n)}=\lim_{n\rightarrow\infty}{n\text{ln }(n)-n+1\over n\text{ln}(n)}=1$; i.e. $\lim_{n\rightarrow\infty}{\ln(n!)\over n\ln(n)}=1$

So by 1), $\ln(n!)=\Theta(n\ln(n))$