How pivot value affects the timing complexity?
Answers
Answered by
1
Answer:
If the pivot divides the array into two pieces of roughly the same size each time, then Quicksort behaves like Mergesort with log n splits of the array. More precisely,
T(n) = f(n) + T(n/2) + T(n/2)
where f(n) is the time taken by Partition. Since Partition compares every key in
A[0 .. (n - 1)]
to the pivot x, the running time for partition is linear, with time complexity f(n) = n. So Quicksort has a time complexity function T given by
T(1) = 1 T(n) =
Similar questions