The Gateway to Computer Science Excellence
+2 votes
368 views
When array is already sorted in reverse order then what will be the recurrence relation for number of swaps on array of n elements using quick sort?
in Algorithms by (21 points) | 368 views
0
it will be,

T(n) = T(n-1) + O(n)
0
Ya it will be T(n)=T(n-1)+O(n)

By solving T(n)=O(n^2)

1 Answer

0 votes
If the array is already sorted and we are using fixed partition method quick sort, then the partition takes place in such a way that one side of the pivot contains n-1 elements and other side contains 0 elements and pivot is in the correct  position that gives recurrence as
T(n)=T(n-1)+n
by (47 points)
0

I m asking if the array is already sorted in reverse order.

0

It does not matter if it is reverse sorted or sorted.If you are choosing the pivot as the last element in either of these cases your sub-problem size shall be T(0) and T(n-1).

https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/overview-of-quicksort

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