MHB Execution Time of QuickSort for Different Inputs

[evinda]

Hello! (Wave)

The following pseudocodes are given.

 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

Which value [m]q[/m] does partition return when all the elements of the array have the same value?

Which is the execution time of [m]quicksort[/m] if all the elements of the array [m]A[/m] have the same value?Show that if [m]A[/m] contains different elements and is sorted in decreasing order, the execution time of [m]quicksort[/m] is $\Theta(n^2)$.Show that the best case running time of [m]quicksort[/m] at an array with pairwise different elements is $O(n \lg n)$ .
I thought that the value that the function [m]partition[/m] returns when all the elements of the array have the same value is equal to $q=n$.In this case $q-1-p+1=q-p=n-p$ and $r-q-1+1=r-q=r-n$, right?So $T(n)=T(n-p)+T(r-n)+\Theta(n)$.Can we suppose that $p=1$ and $r=n$?

 

[evinda]

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

I thought the following:
The if-statement of partition will never be true, so it the function will return $q=1$.
So [m] quicksort(A,1,0) [/m] won't do anything and so the recurrence relation that describes the cost of quicksort will be:
$T(n)=T(n-1)+Θ(n)$.

Am I wrong? Because I found the following: http://www.math.lsa.umich.edu/~lspice/class/416/F2005/tex/2005Math416Homework6Solutions.pdf (page 2)