Quick Sort Algorithm with Constant Partition

Question

I ran into a question about Quick Sort Algorithm. this is take from 2010-midterm exam on data structure from Chinese University, CS 234.

Suppose in Quick Sort, Partition procedure take C times, (consume constant time). if we use random data as input, what is the order (time complexity) of Randomized-Quick Sort?

Anyone could describe the time complexity in this manner?

EDIT:

I calculate these relations. my work is correct? anyone could clarify me?

Best Case: T(n)=2T(n/2)+C= Theta (n)

Worst Case: T(n)=2T(n-1)+C= Theta (n)

Dear @LoïcFaure-Lacroix, I know Theta (n), but I confused how get it ! — user4110176
Good lecture notes here: Analysis of Algorithms I: Randomized Quicksort. I'm not sure what you mean by a "constant partition", though. Each iteration of the of the partition/sort uses a different value. — jww
Dear @jww, suppose we have an algorithm that partition take C times always. now, what is the T(N)? — user4110176
Cross-posted: stackoverflow.com/q/26207040/781723, cs.stackexchange.com/a/29357/755. Please do not post the same question on multiple sites. — D.W.

mrk mrk · Accepted Answer · 2014-10-05T23:04:52

You are looking for the expected running time: expected value of T(n). So let T(n) be the random variable for running time. There are n possible outcomes each of which corresponds to a partition:

T(0) + T(n-1) + c
T(1) + T(n-2) + c
...
T(n-1) + T(0) + c

One of these is going to be picked, let X(i) = 1 if T(i) + T(n - i - 1) + c is picked and 0 otherwise. The recurrence for T(n) can then be written as:

T(n) = X(0)(T(0) + T(n-1) + c) + ... + X(n-1)(T(n-1) + T(0) + c)

Now to calculate the expectation, we write:

E( T(n) ) = E( X(0)(T(0) + T(n-1) + c) + ... + X(n-1)(T(n-1) + T(0) + c) )
          = (1/n)E(2T(0) + 2T(1) + ... + 2T(n-1) + cn)
          = (2/n)(E((T(0)) + ... + E(T(n-1))) + c.

Third line was obtained by linearity of expectation. At this point we are going to guess the answer for E( T(i) ) and use induction to prove it. This technique is called substitution.

Guess: E( T(i) ) <= Ai, for A > 0 and 1 <= i < n.
Base: for i = 1, array is already sorted so expected running time is constant.
Induction: E( T(n) ) <= (2A/n)(n(n-1)/2) = A(n-1) <= An.

So claim holds for n. The expected running time is O(n).

Quick Sort Algorithm with Constant Partition

1 Answers