Question

We have discussed two different variations of Merge Sort (MS), and one of them is

denoted as MS(k), where k is an integer parameter. The main idea of MS(k) is to split an input array into k
subproblems each of the same size, recursively solve each of the k subproblems, and then combine the three
solutions into one sorted array. Recall that in the class, we define the two base cases as follows: if n = 1,
then we output the input array directly; if n = 2, then we can return the input array as it is if it is sorted;
otherwise, we output a reversed version after one swapping. Suppose we re-define the base case of MS(k) as
follows: If a sub-problem has a size no more than a given threshold ∆, then we invoke Bubble Sort (the basic
version) to sort the sub-problem (by default, we assume n is a power of 2 and the term "log" below takes the
base of 2 as well). Please state your results using the Big-Theta notation, i.e., Θ, for all the three questions
below!
a) Consider the case k = 3 and ∆ = log n. Analyze the time complexity of MS(k).
b) Consider the case k = 2 and ∆ = n^1/3. Analyze the time complexity of MS(k).
c) Consider a general case of k and ∆. Analyze the time complexity of MS(k) and state the result as a
function of k and ∆. Here you can assume k is a constant integer (independent of the input size n), while ∆
is an increasing function of n but ∆ = o(n) (e.g., ∆ = log^2 n, ∆ = n/log n).

Answer 1

The time complexity of Merge Sort with k subproblems and a bubble sort threshold Δ depends on the values of k and Δ. For k=3 and Δ=log n, the time complexity is Θ(n^(log 3)). For k=2 and Δ=n^(1/3), the complexity remains Θ(n log n). The general case's complexity is a function of k and the growth rate of Δ.

Step-by-step explanation:

The time complexity of Merge Sort with a variation denoted as MS(k) where it is adapted to split an input array into k subproblems can be analyzed using Big-Theta notation. In this case, the algorithms are also adjusted with a new base case where Bubble Sort is used to sort sub-problems of size no more than a given threshold Δ.

a) Merge Sort with k = 3 and Δ = log n

When k is 3, and the threshold Δ is equal to log n, the time complexity for the recursive part of MS(k) is Θ(n^(log 3)), as each level of recursion splits the problem into 3 parts. However, when sub-problems reach a size of log n, Bubble Sort with time complexity Θ((log n)^2) is applied. Hence the overall time complexity of MS(k) remains dominated by the recursive splitting, resulting in Θ(n^(log 3)).

b) Merge Sort with k = 2 and Δ = n^(1/3)

For k being 2 and the threshold Δ as n^(1/3), the recursive part has a complexity of Θ(n log n). Once the size of sub-problems is n^(1/3), Bubble Sort takes Θ((n^(1/3))^2) = Θ(n^(2/3)) time. Thus, the overall complexity is also Θ(n log n) as it outweighs the time to Bubble Sort the smaller sub-problems.

c) General case of Merge Sort with arbitrary k and Δ

Given an arbitrary constant integer k and a threshold Δ that is an increasing function of n but Δ = o(n), the time complexity of the recursive stage of MS(k) is Θ(n^(log k)). Bubble Sort is applied when sub-problems are at the threshold size of Δ, the complexity of which can vary depending on the growth of Δ as a function of n.