Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Questions  >  In a modified merge sort, the input array is ... Start Learning for Free
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.
  • 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?
Verified Answer
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
Most Upvoted Answer
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'.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

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.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 Description
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.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? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about 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.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? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for 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.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?.
Solutions for 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.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? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE). Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of 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.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? defined & explained in the simplest way possible. Besides giving the explanation of 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.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?, a detailed solution for 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.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? has been provided alongside types of 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.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? theory, EduRev gives you an ample number of questions to practice 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.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? tests, examples and also practice Computer Science Engineering (CSE) tests.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Explore Courses
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev