Why is log(n) in o((n)/(log(n)))? This would be equal to: forall c>0: EE n_0 in NN: forall n>n_0: c log(n)<=(n)/(log(n)) For c=1 this is obvious, because log(n)<=sqrt(n)=(n)/(sqrt(n))<=(n)/(log(n)) This estimation doesn't seem to work for c>1 though. Any ideas on how I could prove it for c>1 ?

Nash Frank

Nash Frank

Answered question

2022-07-17

Why is log ( n ) o ( n log ( n ) )?
This would be equal to:
c > 0 : n 0 N : n > n 0 : c log ( n ) n log ( n )
For c = 1 this is obvious, because
log ( n ) n = n n n log ( n )
This estimation doesn't seem to work for c > 1 though.
Any ideas on how I could prove it for c > 1?

Answer & Explanation

Ragazzonibw

Ragazzonibw

Beginner2022-07-18Added 15 answers

Using limits:
lim n log n n / log n = lim n log 2 n n = 0
because, for example, looking at the real functions log 2 x , x , we have by l'Hospital:
lim x log 2 x x = l'H lim x 2 log x x = l'H lim x 2 x = 0
suchonosdy

suchonosdy

Beginner2022-07-19Added 3 answers

Note that
lim x + ln x x = 0
Therefore also
lim x + ( ln x ) 2 x = 4 lim x + ( ln x ) 2 x = 4 ( lim x ln x x ) 2 = 0.
Especially, for any c > 0 we have ( ln n ) 2 n < 1 c for almost all n, i.e. c ln n < n ln n for almost all n

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?