1. ## Time complexity Help

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,

2. ## Re: Time complexity Help

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.

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: $\displaystyle 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.

3. ## Re: Time complexity Help

Hi,
I assume you know calculus. The following are very often useful:
Let $\displaystyle f(n)$ and $\displaystyle g(n)$ be non-negative functions. Assume
$\displaystyle \lim_{n\rightarrow\infty}{f(n)\over g(n)}=L$

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

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

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

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

$\displaystyle \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

$\displaystyle \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. $\displaystyle \lim_{n\rightarrow\infty}{\ln(n!)\over n\ln(n)}=1$

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