How do we derive complexity of merge sort using its recursive relation? Every wondered how merge sort results in a logarithmic time complexity? How many leaf nodes are in a merge sort recursion tree? How do we know the height of merge sort recursion tree? What does a logarithm time complexity means in the mathematical sense?

The following explanation should demystify all the above questions for you.

Advertisements