@DanielFischer Could I ask you something?
We have the following pseudocodes:
quicksort(A,p,r)
if p<r then
q<-partition(A,p,r)
quicksort(A,p,q-1)
quicksort(A,q+1,r)
partition(A,p,r){
x<-A[r]
i<-p-1
for j<-p to r-1
if A[j]<=x then
i<-i+1
swap(A[i],A[j])
swap(A[i+1],A[r])
return i+1
I want to show that if A contains distinct elements and is sorted in decreasing order, then the execution time of quicksort is $\Theta(n^2)$.