Question: On page 66 there is a high-level description of the quicksort algorithm.

(a) Write down the pseudocode for quicksort.

(b) Show that its worst - case running time on an array of size n is $\mathbf{\Theta }{\left(n\right)}^{\mathbf{2}}$.

(c) Show that its expected running time satisfies the recurrence relation.

$\mathit{T}\left(n\right)\mathbf{\le }\mathit{O}\left(n\right)\mathbf{+}\frac{\mathbf{1}}{\mathbf{n}}\mathbf{\sum }_{\mathbf{i}\mathbf{=}\mathbf{1}}^{\mathbf{n}\mathbf{-}\mathbf{1}}\left(T\left(i\right)+T\left(n-i\right)\right)$

Then, show that the solution to this recurrence is $\mathit{O}\mathbf{(}\mathit{n}\mathbf{}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{n}\mathbf{)}$.

Fast sorting Algorithm:

• Using a divide-and-conquer strategy, Quick Sort sorts the specified array of items.

• Rapid sort randomly chooses a pivot element v. The specified input array is then separated into three sub-arrays: AL, AR, and Av. Where AL represents the sub-array of items lower than v, AR represents the subarray of elements bigger than v, and Av represents the sub-array of elements equal to v.

• After that, Quick sort recursively sorts the two sub-arrays AL,AR.,

(a)

Pseudocode for sorting quickly:

selection sort is a quicksort function (A[1 ...n])

A[1...] is an array of items .n]

A sorted array A [1...] is the output .n]

v= A[k] chose k at random from 1,2,...,n

AL,AR,Av=split AL,AR,Av= (A[1 ...n],v)

quicksort(AL)

quicksort(AR),

(b)

• In the worst-case scenario, rapid sort chooses the biggest member of the array A every time. That is, AR is an empty sub array every time. AL also has a maximum size of n-1.

• As a result, the problem is simply reduced to a subproblem of size n-1 each time.

In the worst-case scenario, the quicksort algorithm will take the following amount of time to run:

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

Expand the above recurrence

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

= T(n-3) + n -2 + n – 1 + n

T(n) = 1+2+3+ .....+n-1+n

=$\frac{n\left(n+1\right)}{2}$

Therefore ,

T(n) = $\frac{n\left(n+1\right)}{2}$ ≤ c.n² = O(n²) for some constant c > 0

T(n) = $\frac{n\left(n+1\right)}{2}$ ≤ c.n² = Ω(n²) for some constant c > 0

Therefore, initial definition of bigT(n) = $\frac{n\left(n+1\right)}{2}$ = Ω(n²)

Therefore, the useless condition of running time of the quicksort on an array of size nisO(n²).

(c)

• Assume that pj is the probability that A[k] is the jth biggest element. 1 ≤ j ≤ n

• pj=1/n so that any component inside the array A could be the jth biggest.

• Also, when the pivot element A[k] is the jth biggest element, suppose Tj is the estimated running time.

• Then total assumption running time, $T\left(n\right)=\sum _{j=1}^n{p}_j{T}_j$

• When the pivot element A[k] is the j^th largest, then A_Lhas at most n-j+1 and A_Rhas at most

• j-1 elements.

• ThusT_j is at most T(n-j+1) + T(i-1) +O(n) .

$$\begin{gathered} T\left(n\right)=\sum _{j=1}^n{p}_j{T}_j \\ \le \sum _{j=1}^n\left(T\left(n-j+1\right)+T\left(j-1\right)+O\left(n\right)\right) \\ \le \frac{1}{2}\sum _{j=1}^n\left(T\left(n-j+1\right)+T\left(j-1\right)+O\left(n\right)\right) \\ \le \frac{1}{2}\sum _{j=1}^{n}O\left(n\right)+\frac{1}{2}\sum _{j=1}^{n}T\left(n-j+1\right)+T\left(j-1\right) \\ \le O\left(n\right)+\frac{1}{2}\sum _{j=1}^{n}T\left(n-i\right)+T\left(i\right) \\ \le cn+\frac{1}{2}\sum _{j=1}^{n}T\left(n-i\right)+T\left(i\right) \end{gathered}$$

Hence $T\left(n\right)\le O\left(n\right)+\frac{1}{n}\sum _{j=0}^{n-1}T\left(n-i\right)+T\left(i\right)$ ------(1)

To show that T(n) = O(n log n), use induction.

Assume T(n) = O(n log n) implies T(n) ≤ bn log n ------(2)

Re write equation(1) as follows:

$T\left(n\right)\le cn+\frac{2}{n}\sum _{j=0}^{n/2}T\left(n-i\right)+T\left(i\right)$

From inductive hypothesis(equation(2)),

$$\begin{gathered} T\left(n\right)\le cn+\frac{2b}{n}\left[\sum _{j=0}^{n/2}\left(n-i\right)\log \left(n-i\right)+i\log i+\sum _{j=0}^{n/2}\left(n-i\right)\log \left(n-i\right)+i\log i\right] \\ T\left(n\right)\le cn+\frac{2b}{n}[\sum _{j=0}^{n/2}\left(n-i\right)\log \left(n-i\right)+i\log i \end{gathered}$$

Again, re write above in equation as follows:

$T\left(n\right)\le cn+\frac{2b}{n}[\sum _{j=1}^{n/4}\left(n-i\right)\log \left(n-i\right)+i\log i+\sum _{j=0}^{n/2}\left(n-i\right)\log \left(n-i\right)+i\log i]$

Therefore, by induction, it is proved that the solution has run time of $O\left(n\log n\right)$.