Show Worst Case Running Time Quick Select N Element Sequence N2 Q37126645

Show that the worst-case running time of quick-select on ann-element sequence is Ω(n2).

Solution

`Hey,

Note: Brother in case of any queries, just comment inbox I would be very happy to assist all your queries

The worst case happens when the pivot is always theextreme element.

So,

T(n)=T(n-1)+cn

So,

T(n)=T(0)+c*(n+(n-1)+…..+2+1)

So,

T(n)=c*(n*(n+1)/2)

So,

T(n)=theta(n^2) which states thatT(n)=Omega(n^2)

Kindly revert for any queries

Thanks.