Imagine that there exists an algorithm \(SPLIT_k\) that can split a list \(L\) of \(n\) elements into \(k\) sublists, each containing one or more elements, such that sublist \(i\) contains only elements whose values are less than all elements in j for i

Furthermore, assume that the k lists can be concatenated again in constant time. Consider the following algorithm:

(a) What is the worst-case asymptotic running time for SORTk? Why?

(b) What is the average-case asymptotic running time of SORTk? Why?

Transcribed Image Text:

List SORTK (List L) { List sub [k]; // To hold the sublists if (L. length() > 1) { SPLITK (L, sub); // SPLITK places sublists into sub for (i=0; i