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: .

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 and be non-negative functions. Assume

1. If then and so also and .

2. If L=0, then , but (and so

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

Example:

Recall and so

By approximating Riemann sums and the fact that ln is increasing,

With a little more argument, you can see that

; i.e.

So by 1),