In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. What is the worst case time complexity of this merge sort?a)N(logN base 3)b)N(logN base 2/3)c)N(logN base 1/3)d)N(logN base 3/2)Correct answer is option 'D'. Can you explain this answer?

Question

Answer

Explanation:

In a modified merge sort, the input array is split at a position one-third of the length(N) of the array. This means that at each level of recursion, the array is divided into three subarrays of approximately equal size.

Time Complexity of Merge Sort:
In a standard merge sort algorithm, the time complexity is given by O(NlogN), where N is the size of the array.

Analysis of Modified Merge Sort:
In the modified merge sort, the input array is split into three subarrays of approximately equal size. Let's denote the size of the array as N.

At each level of recursion, the array is divided into three subarrays of size N/3. The merge sort algorithm is then applied to these subarrays.

Number of Levels:
The number of levels in the recursion tree can be determined by finding the height of the tree. At each level, the size of the array is divided by 3.

The number of levels (h) can be calculated as follows:
N/(3^h) = 1 (when the array is divided into subarrays of size 1)
N = 3^h
Taking logarithm base 3 on both sides:
log3(N) = log3(3^h)
log3(N) = h

So, the height of the recursion tree is log3(N).

Number of Subproblems:
At each level of recursion, the array is divided into three subarrays. So, the number of subproblems at each level is 3.

Time Complexity Calculation:
To calculate the time complexity, we need to consider the number of levels and the number of subproblems at each level.

At each level, there are 3 subproblems, and the total number of levels is log3(N).

So, the time complexity can be calculated as:
3^0 + 3^1 + 3^2 + ... + 3^(log3(N))

Using the formula for the sum of a geometric series, we can simplify this expression:

3^0 + 3^1 + 3^2 + ... + 3^(log3(N)) = (3^(log3(N)+1) - 1) / (3 - 1)
= (3 * 3^(log3(N)) - 1) / 2
= (3 * N - 1) / 2

Therefore, the worst-case time complexity of this modified merge sort is O(N).

Conclusion:
The worst-case time complexity of the modified merge sort, where the input array is split at a position one-third of the length(N) of the array, is N(logN base 3/2).

Similar Computer Science Engineering (CSE) Doubts

In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. What is the worst case time complexity of this merge sort?

In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. Which of the following is the tightest upper bound on time complexity of this modified Merge Sort.

In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. Which of the following is the tightest upper bound on time complexity of this modified Merge Sort.

In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. Which of the following is the tightest upper bound on time complexity of this modified Merge Sort.

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

Top Courses for Computer Science Engineering (CSE)

Top Courses for Computer Science Engineering (CSE)

Suggested Free Tests

Related Content

Mock Test Series

Subject-wise Courses

Subject-wise Courses

Other Engg Branches

Company