w3hello.com logo
Home PHP C# C++ Android Java Javascript Python IOS SQL HTML videos Categories
Choosing minimum length k of array for merge sort where use of insertion sort to sort the subarrays is more optimal than standard merge sort

Well, this is a mathematical minimization problem, and to solve it, we need some basic calculus.

We need to find the value of k for which d[n*k + n*lg(n/k)] / dk == 0.

We should also check for the edge cases, which are k == n, and k == 1.

The candidate for the value of k that will give the minimal result for n*k + n*lg(n/k) is the minimum in the required range, and is thus the optimal value of k.

Attachment, solving the derivitives equation:

d[n*k + n*lg(n/k)] / dk = d[n*k + nlg(n) - nlg(k)] / dk
= n + 0 - n*1/k = n - n/k 
n - n/k = 0 => n = n/k => 1/k = 1 => k = 1

Now, we have the candidates: k=n, k=1. For k=n we get O(n^2), thus we conclude optimal k is k == 1.

Note that we found the derivitives on the function from the big Theta, and not on the exact complexity function that uses the needed constants.
Doing this on the exact complexity function, with all the constants might yield a bit different end result - but the way to solve it is pretty much the same, only take derivitives from a different function.

© Copyright 2018 w3hello.com Publishing Limited. All rights reserved.