Welcome to the Treehouse Community
Looking to learn something new?
Shouldn't Merge Sort be O(n * log(n) + log(n))
When you think about the Merge Sort you split the set ( log(n) ) and then you join them together while sorting each group (n * log(n)). In sum that such be log(n) + n * log(n)
Clayton PerszykTreehouse Moderator 48,107 Points
Not sure, but this looks like a good explanation: https://softwareengineering.stackexchange.com/questions/297160/why-is-mergesort-olog-n
The reason that O(n*log(n)+log(n)) simplifies to just O(n*log(n)) is that the limit as n approaches infinity of the ratio of n*log(n)+log(n) to n*log(n) is 1. In other words, as we make the size of the input set arbitrarily large, the rate of growth of n*log(n)+log(n) and n*log(n) is 'almost exactly' the same so we just write O(n*log(n)). I hope this helps, I don't think this course is intended to get into the weeds with calculus but limits aren't too hard to understand intuitively. Overlaying the graphs of nlog(n) and nlog(n) + log(n) for large n as in the video examples might help to illustrate the point.