The Gateway to Computer Science Excellence

0 votes

In quick sort for sorting of n Numbers, the 75th greatest Element is selected as pivot using $O(n^2)$ time complexity algorithm than what is the worst case time complexity of quick sort.

- O($n^2$)
- O($n^3$)
- O(nlogn)
- O(n)

0

What i think is-

There is no need to select 75th greatest element as pivot.. because its its searching itself takes O(n²) time..

Whatever pivot is selected quick sort worst case O(n^2).

There is no need to select 75th greatest element as pivot.. because its its searching itself takes O(n²) time..

Whatever pivot is selected quick sort worst case O(n^2).

0

Whatever pivot is selected quick sort worst case O(n^2)

but here it is given that this procedure takes $O(n^2)$ time and in original quick sort, it takes O(1) time because we go to that index in array and select it and then do the partition procedure. Here, I think, we have to include $O(n^2)$ in recurrence.

So, recurrence will look like $T(n) = T(74) +T(n-75) + O(n^2) + O(n)$

O(n^2) to select pivot then partition will take O(n) time and after partition, 74 elements which are right of 75th greatest elements will be more than 75th greatest element and elements on left side will be less than that 75th greatest element. Now here T(74) will be constant(c) and now we have to solve recurrence to find running time.

please correct me if I am wrong.

0

Yes, answer is O($n^2$).

But I am not getting why recurrence relation is different if 75th minimum element is selected as pivot is given.

But I am not getting why recurrence relation is different if 75th minimum element is selected as pivot is given.

0

$T(n)=T(n-75)+T(74)+O(n^2)+O(n)$

it will lead to $O(n^3)$ right?

Whatever pivot is selected quick sort worst case O(n^2).

That was unconsciously written..

We can chose first or last element as pivot..$T(n)=T(n-1)+T(0)+O(n)=O(n^2)$

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,375 answers

198,519 comments

105,311 users