MHB Worst-case running time of algorithm

[mathmari]

Hey!

Let the quicksort algorithm be the following:

procedure QUICKSORT(S)
         if S contains at no one element then return S
         else
            begin
               choose an element a randomly from S;
               let S1, S2 and S3 be the sequences of elements in S less than, equal to and greater than a, respectively;
               return (QUICKSORT(S1) followed by S2 followed by QUICKSORT(S3))
            end

How can I show that the worst-case running time of Quicksort is $O(n^2)$ ?? (Wondering)

 

[johng1]

choose an element a randomly from S; let S1, S2 and S3 be the sequences
of elements in S less than, equal to
and greater than a, respectively;

The above is a description of a partitioning algorithm. It can be shown that the best partitioning algorithm has order $\Theta (n)$ where n is the number of elements of S. Suppose all elements of S are different and at each call to partition (unluckily) the pivot a is the smallest element. Then the total order of quicksort is $$n+\Theta (n)+\Theta(n-1)+\cdots +\Theta(1)=\Theta(n^2)$$

 

[mathmari]

So, to show that the worst-case running time of Quicksort is $O(n^2)$ do we have to say just the following:

Suppose all elements of S are different and at each call to partition (unluckily) the pivot a is the smallest element. Then the total order of quicksort is $$n+\Theta (n)+\Theta(n-1)+\cdots +\Theta(1)=\Theta(n^2)$$

?? (Wondering)

Or do we have to justify it further, for example with a recurrence relation?? (Wondering)