A variant of merge sort called a-to-b merge sort(A,low,high)always divides the unsorted segment of the array A from the index low to high in the ratio a:b instead of making 1:1 division.Compute the time complexity of a-to-b merge sort. I tried to solve and obtained this: T(n)=aT(n/b)+O(n).By master theorem, A)If a>b T(n)=O(n^(loga/logb)(B)If a=b T(n)=O(n^(loga/logb)*n)(C)If a<b T(n)=O(n^(loga/logb)Is this solution correct?
To make the math easier, instead of thinking of an a:b ratio for the split, let's suppose that you have a fractional split that puts an ε fraction of the elements in one subcall and the remaining (1-ε) fraction in the other. For simplicity, we'll assume that 1-ε ≥ ε so that we can talk about a larger and smaller half of the array.
With this modified merge sort, there's still linear work done per call, plus the work required to do two recursive calls, one on εn elements and one on (1-ε)n elements. This means that we have the recurrence relation
T(n) = T(εn) + T((1-ε)n) + O(n)
So what does this recurrence solve to? Well, there are a few different ways we can think about this. I think the easiest option would be to imagine a recursion tree and to count the work per level.
Imagine we have a really large n and think about what shape the recursion tree will take. At the top level, we have a single call of size n. On the level below, we have one call of size εn and one of size (1-ε)n. Below that we have one call of size ε2n, two of size ε(1-ε)n, and one of size (1-ε)2n. (This would be a great time to take out a sheet of paper and draw this out so that you can see what's going on - with a visual, this will make tons of sense).
This may sound Hairy and Scary, but it's actually not so bad. Remember that the work done by each call is O(n), so we can determine the work per level by summing up all the work done by all the calls in each individual layer of the tree. The top layer has one call of size n, so there's O(n) work done. If you sum up the sizes of all the calls in the second layer, you'll see that it works out to n as well, so the total work done in that layer is O(n). The math is a bit harder in the third layer, but the size of all the calls also works out to n, so O(n) total work is done in that layer as well. (Again, check this on your own to confirm you see why!)
Turns out that this isn't a coincidence. Notice that each recursive call splits the array cleanly into two pieces and recurs on each individually, so as we go from one layer to the next, the total sizes of the arrays in the sub calls should always total n. (Well, mostly. Eventually the arrays get so small that the recursion bottoms out, but more on that in a minute). That means that we're doing O(n) work per level, so the total work done is going to be O(n) times the number of layers. So what's that?
Well, as with many divide and conquer algorithms, notice that in this algorithm, the size of each subarray is always a constant fraction smaller than the original array. Whenever you see this pattern, you should quickly jump to the conclusion that after O(log n) steps, the array shrinks to size one and we're done. Why? Because if you repeatedly divide by a constant, it takes O(log n) iterations to shrink to size one.
Overall, this very rough analysis tells us that the runtime should be O(n log n): O(n) work per layer and O(log n) layers.
Now, there are some concerns to watch for here because the recursion tree has a slightly weird shape. Specifically, since the split isn't balanced, the tree will not be a complete binary tree, with the branches that shrink by a factor of ε bottoming out before the branches that shrink by a factor of (1-ε). This isn't a problem, though. If we pretend that all of those missing calls still happen anyway, we end up with an over approximation of the total work done, so our O(n log n) bound at worst overstates the runtime. It turns out to be asymptotically tight. One way to see this is that there are O(log n) layers before the branch that shrinks by a factor of ε dies out and in the part of the tree corresponding to that region we know that O(n log n) work is done.
This looks like homework, so I'll leave as an exercise the details of filling in all the gaps and working out the base of all the logarithms. Good luck!