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:
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).
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