In a modified merge sort, the input array is splitted at a position on...
The time complexity is given by: T(N) = T(N/3) + T(2N/3) + N Solving the above recurrence relation gives, T(N) = N(logN base 3/2)
View all questions of this test
In a modified merge sort, the input array is splitted at a position on...
Introduction:
The modified merge sort splits the input array at a position one-third of the length (N) of the array. We need to determine the tightest upper bound on the time complexity of this modified merge sort.
Explanation:
Merge sort is a divide-and-conquer algorithm that divides the array into two halves, sorts them recursively, and then merges the sorted halves. The time complexity of traditional merge sort is O(NlogN).
In the modified merge sort, the input array is split at a position one-third of the length (N) of the array. Let's analyze the time complexity of this modified merge sort.
Splitting the array:
When the array is split at one-third of its length, the size of the left subarray is N/3 and the size of the right subarray is 2N/3.
Merging the subarrays:
The merging process in merge sort takes linear time. In the modified merge sort, the left subarray of size N/3 is merged with the right subarray of size 2N/3. The merging process will take O(N) time.
Recurrence relation:
The recurrence relation for the modified merge sort can be expressed as:
T(N) = 2T(2N/3) + O(N)
In the modified merge sort, each recursive call processes 2/3 of the original array size.
Applying the master theorem:
To determine the time complexity of the modified merge sort, we can apply the master theorem.
The master theorem states that if a recurrence relation is of the form:
T(N) = aT(N/b) + f(N)
Where a >= 1, b > 1, and f(N) is an asymptotically positive function, then the time complexity can be determined as follows:
1. If f(N) = O(N^c) where c < logb(a),="" then="" t(n)="" />
2. If f(N) = Θ(N^c log^kN) where c = logb(a), then T(N) = Θ(N^c log^(k+1)N).
3. If f(N) = Ω(N^c) where c > logb(a), if af(N/b) <= kf(n)="" for="" some="" constant="" k="">=>< 1="" and="" sufficiently="" large="" n,="" then="" t(n)="" />
For the modified merge sort, a = 2, b = 3/2, and f(N) = O(N).
The value of c is logb(a) = log(3/2) = log3 - log2 ≈ 0.58496.
Since f(N) = O(N^c) where c < logb(a),="" we="" can="" apply="" case="" 1="" of="" the="" master="" />
Therefore, the tightest upper bound on the time complexity of the modified merge sort is N^(log3/log(3/2)) ≈ N^(2.70951) ≈ N^(logN base 3/2).
Conclusion:
The tightest upper bound on the time complexity of the modified merge sort is N(logN base 3/2), which matches option 'D'.
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).