CODEWITHSUNDEEP
complexity-theory
Ritika Gupta
Ritika Gupta

Reputation: 573

O(n*log n) + O(m*log m) vs O((n+m)log(n+m))

Which complexity is better O(n*log n) + O(m*log m) vs O((n+m)log(n+m)) where n>1 and m>1. Can anyone give mathematical proof also?

Upvotes: 0

Views: 504

Answers (1)

Erich Kitzmueller
Erich Kitzmueller

Reputation: 36987

Here is my reasoning why I think they are equally good:

Case A: both m and n grow equally fast:

O(n*log n) + O(m*log m) = 2*O(n*log n) = O(n*log n)   // positive constant removed
O((n+m)log(n+m)) = O((2n)log(2n)) = O((n)log(n))      // positive constants removed

Case B: either m or n grows faster than the other (assuming n, w.l.o.g.)

O(n*log n) + O(m*log m) = O(n*log n)    // slower growing part removed
O((n+m)log(n+m)) = O(n*log n)           // slower growing part removed

Upvotes: 1

Related Questions