The Gateway to Computer Science Excellence
+1 vote
1.8k views
the worst case time complexity of quicksort for an elements when the median is selected as the pivot

a. o(n^2)

b.o(n)

c.o(nlogn)

d.o(logn)
in Algorithms by (17 points) | 1.8k views

1 Answer

+3 votes
Best answer
Answer C) O(nlogn),  when median selected as pivot, partition method will divide array into equal halves.. so logn level recursion tree will form with cn work(partition method)  at each level..
The recurence would be..
T(n) = 2T(n/2) + Θ(n)
Therefore total time complexity =Θ(nlogn)  in all cases

Note:O(n) time algo available for median finding
https://en.m.wikipedia.org/wiki/Median_of_medians
by Loyal (8.2k points)
edited by
0
can you tell the algo, which gives median in O(n) time?
+1
0
Thanks :)
0
What if all elements are equal
0
then also O(nlogn)
0
@prashant can u explain. How it will be O(nlogn) when all elements are same
0
same recurrence relation will be applied here also
0
if all elements are same then worst case partitioning will occur. How O(nlogn) then?
0
Here it doesn't matter all the elements are same or not because it will divide the array in two equal parts which gives the recurrence relation for best case of quick sort

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,492 answers
195,439 comments
100,703 users