Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Questions > Suppose we have a O(n) time algorithm that fi...
Start Learning for Free
Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.
- a)O(n^2 Logn)
- b)O(nLogn)
- c)O(n Logn Logn)
- d)none
Correct answer is option 'B'. Can you explain this answer?
| FREE This question is part of | Download PDF Attempt this Test |
Verified Answer
Suppose we have a O(n) time algorithm that finds median of an unsorted...
When we choose median as pivot element then after the partition algorithm it will go in the middle of the array having half of the elements to left the left and half in the right.
Thus after partition algorithm the array will be divided into two equal parts of n/2 elements each.
Hence the resultant recurrence relation would be-
T(n) = O(n) (for selecting median) + O(n) (for partition) + T(n/2) + T(n/2)
T(n) = O(n) + 2T(n/2)
We can solve the above recurrence relation using master method
Hence, the correct answer is Option B
You can solve more such questions by going through the link:
Most Upvoted Answer
Suppose we have a O(n) time algorithm that finds median of an unsorted...
Explanation:
- QuickSort is an efficient sorting algorithm with average case complexity of O(nLogn). However, its worst case complexity is O(n^2) when the pivot selected is either the smallest or largest element in the array, resulting in unbalanced partitions.
- To improve the efficiency of QuickSort, we can use a better pivot selection strategy. One such strategy is to choose the median element as the pivot, which ensures that the partitions are roughly equal in size and reduces the chances of worst case scenario.
- If we have an O(n) time algorithm to find the median element of an unsorted array, we can use it to select the pivot in QuickSort. This will result in a modified version of QuickSort with improved worst case complexity.
- The worst case scenario for this modified QuickSort will occur when the median element is selected as the pivot and it still results in unbalanced partitions. This can happen if the array is already sorted or has many duplicate elements, such that the median element is either the smallest or largest element in the array.
- In this worst case scenario, the time taken by the median finding algorithm will be O(n), and the time taken by QuickSort will be O(n^2), resulting in a worst case time complexity of O(n^2).
- However, this worst case scenario is unlikely to occur in practice, and the average case complexity of the modified QuickSort will still be O(nLogn).
- Therefore, the correct answer is option B, O(nLogn).
- QuickSort is an efficient sorting algorithm with average case complexity of O(nLogn). However, its worst case complexity is O(n^2) when the pivot selected is either the smallest or largest element in the array, resulting in unbalanced partitions.
- To improve the efficiency of QuickSort, we can use a better pivot selection strategy. One such strategy is to choose the median element as the pivot, which ensures that the partitions are roughly equal in size and reduces the chances of worst case scenario.
- If we have an O(n) time algorithm to find the median element of an unsorted array, we can use it to select the pivot in QuickSort. This will result in a modified version of QuickSort with improved worst case complexity.
- The worst case scenario for this modified QuickSort will occur when the median element is selected as the pivot and it still results in unbalanced partitions. This can happen if the array is already sorted or has many duplicate elements, such that the median element is either the smallest or largest element in the array.
- In this worst case scenario, the time taken by the median finding algorithm will be O(n), and the time taken by QuickSort will be O(n^2), resulting in a worst case time complexity of O(n^2).
- However, this worst case scenario is unlikely to occur in practice, and the average case complexity of the modified QuickSort will still be O(nLogn).
- Therefore, the correct answer is option B, O(nLogn).
Attention Computer Science Engineering (CSE) Students!
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).
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Similar Computer Science Engineering (CSE) Doubts
Top Courses for Computer Science Engineering (CSE)View all
Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.a)O(n^2 Logn)b)O(nLogn)c)O(n Logn Logn)d)noneCorrect answer is option 'B'. Can you explain this answer?
Question Description
Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.a)O(n^2 Logn)b)O(nLogn)c)O(n Logn Logn)d)noneCorrect answer is option 'B'. 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 Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.a)O(n^2 Logn)b)O(nLogn)c)O(n Logn Logn)d)noneCorrect answer is option 'B'. 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 Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.a)O(n^2 Logn)b)O(nLogn)c)O(n Logn Logn)d)noneCorrect answer is option 'B'. Can you explain this answer?.
Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.a)O(n^2 Logn)b)O(nLogn)c)O(n Logn Logn)d)noneCorrect answer is option 'B'. 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 Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.a)O(n^2 Logn)b)O(nLogn)c)O(n Logn Logn)d)noneCorrect answer is option 'B'. 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 Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.a)O(n^2 Logn)b)O(nLogn)c)O(n Logn Logn)d)noneCorrect answer is option 'B'. Can you explain this answer?.
Solutions for Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.a)O(n^2 Logn)b)O(nLogn)c)O(n Logn Logn)d)noneCorrect answer is option 'B'. 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 Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.a)O(n^2 Logn)b)O(nLogn)c)O(n Logn Logn)d)noneCorrect answer is option 'B'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.a)O(n^2 Logn)b)O(nLogn)c)O(n Logn Logn)d)noneCorrect answer is option 'B'. Can you explain this answer?, a detailed solution for Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.a)O(n^2 Logn)b)O(nLogn)c)O(n Logn Logn)d)noneCorrect answer is option 'B'. Can you explain this answer? has been provided alongside types of Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.a)O(n^2 Logn)b)O(nLogn)c)O(n Logn Logn)d)noneCorrect answer is option 'B'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.a)O(n^2 Logn)b)O(nLogn)c)O(n Logn Logn)d)noneCorrect answer is option 'B'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
|
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Suggested Free Tests
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
Follow Us
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup