Is O ( n log &#x2061;<!-- ⁡ --> n ) always smaller than O ( m )

slijmigrd

slijmigrd

Answered question

2022-07-07

Is O ( n log n ) always smaller than O ( m ) for n 1 < m < n 2 ?
I am writing an algorithm that needs to finish in O ( m ). The problem is for a graph G ( V , E ), where m = | E | and n = | V | . m can be in the range of n 1 to n 2 1
If I do some processing that takes O ( ( n 3 ) log ( n 3 ) ) time, will that still satisfy being smaller than O ( m ) or not?
Thanks

Answer & Explanation

torpa6d

torpa6d

Beginner2022-07-08Added 7 answers

m > n 1 implies that ( n 3 ) log ( n 3 ) < ( m 2 ) log ( m 2 ). That is O ( m log m ), but not O ( m ).

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?