The Gateway to Computer Science Excellence
0 votes
56 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 (257 points)
edited by | 56 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

Please log in or register to answer this question.

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,709 users