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,

Printable View

- Nov 16th 2013, 02:51 PMzevelBenTime 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 PMemakarovRe: Time complexity Help
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.

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. - Nov 17th 2013, 07:35 PMjohngRe: 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))$