Recently I stumbled upon this problem from Introduction To Algorithms Edition 3
Problem 2-1:
Although merge sort runs in O(n logn) worst-case time and insertion sort runs in O(n^2), the latter runs faster for small problem sizes. Consider a modification to Merge Sort in which n/k sublists of length k are sorted using insertion sort and then merged using standard merging mechanism.
(A) Show that insertion sort can sort the n/k sublists, each of length k, in O(nk) worst-case time.
The answer given is:
Ans: Insertion sort takes (k^2) time per k-element list in the worst case. Therefore,
sorting n/k lists of k elements each takes (k^2 n/k) = (nk) worst-case time
How do they get (k^2 n/k) from the given data?? Im not understanding this at all and would greatlly appreciate an explanation.