The Gateway to Computer Science Excellence
0 votes
109 views

Consider the following inputs:

1) 2 2 2 2 2 2 2

2) 1 2 3 4 5 6 7

3) 7 6 5 4 3 2 1

In all three cases, the worst-case time complexity of quicksort is O(n2)

 

My doubt is if I am taking the middle element as a pivot, then my recursive equation for the above three cases will become: T(n) = T(n/2) + O(n), right?

Can someone explain how we are saying worst-case time complexity for these three cases is O(n2) irrespective of the selection of the pivot element?

 

in Algorithms by
edited by | 109 views
0
I don't think you should get worst case if you take the middle element as the pivot. What is the source of your claim?
0
it is basic question refer to theory again
0
@Gurdeep, Sir, Can you please provide a proper explanation for the above scenario
0
@garvit

dont call me sir  

have sent you a link( personal message) watch lecture 9 and 10 both yor will get everything about quick sort

1 Answer

0 votes
we get best case when we select median element as pivot and not middle element. fixing any position in the array as pivot may give worst case O(n^2).that is why randomised quick sort performs better coz u don't fix pivot position.
by
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
52,315 questions
60,436 answers
201,775 comments
95,252 users