Question

Prove it's correct or wrong.

A particular version of PARTITION runs in logarithmic time but produces splits where all elements go to the same side of the pivot every time. QUICKSORT based on this PARTITION has the same worse-case running time as the standard version.

Answer 1

Hi,

---------------------------------------------------

Standard Quick Sort

1.if partiotion time is O(N) and produces splits where all elements go to the same side of the pivot every time. QUICKSORT based on this PARTITION has the same worse-case running time O(N²)

T(n)=T(N-1)+O(N)

= (N)+(N-1)+(N-2)+......+3+2+1

=(N)(N+1)/2

≈O(N²)

------------------------------------------

Modified Quick Sort ( when PARTITION runs in logarithmic time)

2.if partiotion time is O(logN) and produces splits where all elements go to the same side of the pivot every time. QUICKSORT based on this PARTITION has worst case running time O(NlogN) so QUICKSORT based on this PARTITION has not the same worse-case running time as the standard version.

T(n)=T(N-1)+O(logN)

=logN+log(N-1)+log(N-2)+log(N-3)+.......+ log3+log2+log0

=log(N*(N-1)*(N-3)*.....*3*2*1)

≈log(N^N)

≈O(NlogN)

---------------------------------------------------------

Still if you have any doubt or need any kind of improvement, please let me know in comment section and if you like, Please upvote.

Thank You !