9.
Texas Instruments technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Sorting an array**
Consider the following algorithm to sort an array.
function MergeSort(A, n) //A[1:n] is an array of n integers
if (n==1)
return (A)
else if (n==2)
return ( min(A[1],A[2]), max(A[1],A[2]))
else begin
B = MergeSort(A[1:floor(n/2)], floor(n/2))
C = MergeSort(A[ceil(n/2)],n], ceil(n/2))
return (Merge(B,C))
end
endfunct```
Analyse the algorithm and determine the complexity of the function **MergeSort()** if the complexity of **Merge()** is **O(n)**.
Show answer & explanation
The provided algorithm is a standard implementation of Merge Sort. The time complexity of Merge Sort is governed by the recurrence relation T(n) = 2T(n/2) + O(n), which solves to O(n log n). Since O(n log n) is not listed among options A, B, or C, the correct choice is 'None of these'.
Step-by-step Derivation:
Step 1: Identify the recurrence relation from the pseudocode. The function splits the array into two halves (size n/2), recursively calls itself on both halves, and then calls the Merge function.
Step 2: Define the recurrence: T(n) = 2T(n/2) + f(n), where f(n) is the complexity of the Merge function.
Step 3: Given that the complexity of Merge() is O(n), the recurrence becomes T(n) = 2T(n/2) + O(n).
Step 4: Apply the Master Theorem. Here, a = 2, b = 2, and f(n) = n^k where k = 1. Since log_b(a) = log_2(2) = 1, and k = 1, we are in Case 2 of the Master Theorem.
Step 5: The solution for Case 2 is T(n) = O(n^(log_b a) * log n) = O(n^1 * log n) = O(n log n).
Step 6: Compare O(n log n) with the given options: A) O(n^2), B) O(n^3), C) O(n). None of these match O(n log n).