how to show that 5n=O(nlogn)

I have this as a 开发者_如何学编程homework question and don't remember learning it in class. Can someone point me in the right direction or have documentation on how to solve these types of problems?

More formally...

First, we prove that if f(n) = 5n, then f ∈ O(n). In order to show this, we must show that for some sufficiently large k and i ≥ k, f(i) ≤ ci. Fortunately, c = 5 makes this trivial.

Next, I'll prove that for all f ∈ O(n) that f ∈ O(n * log n). Hence, we must show that for some sufficiently large k, all i ≥ k, f(i) ≤ ci * log i. Hence, if we let k be large enough that f(i) ≤ ci, and i ≥ 2, then the result is trivial since ci ≤ ci * log i.

QED.

Look into the definition of big-O-notation. It means that 5n will run no slower the nlogn, which is true. nlogn is an upper bound of the number of operations to be performed.

You can prove it by applying L'Hopitals rule to lim n-> infinity of 5n/nlogn

g(n) = 5n and f(n)=nlogn

Derivate g(n) and f(n) so you will get something like this

5/(some stuff here that will contain n)

5/infinity = 0 so 5n = O(nlogn) is true

I don't remember the wording of the formal definition, but what you have to show is:

c₁ * 5 * n < c₂ * n * logn, n>c₃

where c₁ and c₂ are arbitrary constants, for some number c₃. Define c₃ in terms of c₁ and c₂, and you're done.

It's been three years since I touched big-O stuff. But I think you can try to show this:

O(5n) = O(n) = O(nlogn)

O(5n) = O(n) is very easy to show, so all you have to do now is to show O(n) = O(nlogn) which shouldn't be too hard too.