Home > Mobile >  Proof of merge sort time complexity when input size is not a power of 2?
Proof of merge sort time complexity when input size is not a power of 2?

Time:10-02

I'm aware that the time complexity of merge sort is O(nlogn), but every proof I have seen involves considering the running time of merge sort to be T(n) = 2T(n/2) O(n) for n>1, and T(n) = O(1) for n=1. However, this recursion tree proof would only work when n is a power of 2, as T(n) is only defined on integers. What would the proof be for the more general case when we don't just assume the input size is a power of 2?

CodePudding user response:

Imagine your input size is n = 2m k, where k < 2m.

Then you can just add as many extra values to your list as you need to make the size 2m 1 (padding), then sort this array and pluck your dummy values back out at the end. Now, your list indeed has the length of a power of two, so you can run mergesort the way you are used to, and in O(2m 1 log(2m 1)) time.

Well, 2m 1 = 2 * 2m <= 2n, so your runtime is now O(2n log(2n)) = O(n log n).

In conclusion, padding your list with enough values to turn it into a power of two will increase it with a factor <2, so by the properties of big-O notation, it is still in the same complexity class.

  • Related