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:
In the modified merge sort, the input array is divided into two parts at a position one-third of the length of the array. This modified version alters the traditional merge sort algorithm, which splits the array into two equal halves. We need to find the tightest upper bound on the time complexity of this modified merge sort.
Explanation:
To analyze the time complexity of the modified merge sort, let's consider the recursive nature of the algorithm. The algorithm can be divided into two main parts:
1. Splitting the array:
- In each recursive call, the array is split into two parts at a position one-third of the length of the array.
- This splitting process takes O(N) time, where N is the length of the array.
2. Merging the sorted subarrays:
- After the array is split into subarrays, they are recursively sorted and then merged.
- The merge operation takes O(N) time, as it needs to compare and merge two sorted subarrays.
Time Complexity Analysis:
Let's analyze the time complexity of the modified merge sort algorithm:
- At each recursive level, the array is divided into two parts at a position one-third of the length of the array.
- The number of recursive levels can be calculated as log base 3 of N, where N is the length of the array.
- In each level, the merge operation takes O(N) time.
Hence, the overall time complexity of the modified merge sort can be expressed as:
T(N) = O(N) * log base 3 of N
Comparison with the Given Options:
Now, let's compare the derived time complexity with the given options to find the tightest upper bound:
a) N(logN base 3): The derived time complexity is O(N * log base 3 of N), which matches with option a.
b) N(logN base 2/3): The derived time complexity is not in the form of N * log base 2/3 of N, so option b is not the correct answer.
c) N(logN base 1/3): The derived time complexity is not in the form of N * log base 1/3 of N, so option c is not the correct answer.
d) N(logN base 3/2): The derived time complexity is in the form of N * log base 3 of N, which matches with option d.
Conclusion:
After comparing the derived time complexity with the given options, we can conclude that the tightest upper bound on the time complexity of the modified merge sort is option d) N(logN base 3/2).
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).