- #1
mathmari
Gold Member
MHB
- 5,049
- 7
Hey!
Let the quicksort algorithm be the following:
How can I show that the worst-case running time of Quicksort is $O(n^2)$ ?? (Wondering)
Let the quicksort algorithm be the following:
Code:
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)