The Gateway to Computer Science Excellence
+2 votes
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
it will be,

T(n) = T(n-1) + O(n)
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
by (47 points)

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


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).

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