Matrix Multiplication / Quick Sort

Outline (1)

• Matrix Multiplication

  • Traditional

  • Recursive

  • Strassen

Outline (2)

• Quicksort

  • Hoare Partitioning

  • Lomuto Partitioning

  • Recursive Sorting

Outline (3)

• Quicksort Analysis

  • Randomized Quicksort

  • Randomized Selection

    • Recursive

    • Medians

Matrix Multiplication (1)

• Input: $A=[a_{ij}],B=[b_{ij}]$
• Output: $C=[c_{ij}]=A \cdot B$ $\Longrightarrow i,j=1,2,3, \dots, n$

$$\begin{bmatrix} c_{11} & c_{12} & \dots & c_{1n} \\ c_{21} & c_{22} & \dots & c_{2n} \\ \vdots & \vdots & \vdots & \ddots \\ c_{n1} & c_{n2} & \dots & c_{nn} \\ \end{bmatrix} = \begin{bmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \vdots & \ddots \\ a_{n1} & a_{n2} & \dots & a_{nn} \\ \end{bmatrix} \cdot \begin{bmatrix} b_{11} & b_{12} & \dots & b_{1n} \\ b_{21} & b_{22} & \dots & b_{2n} \\ \vdots & \vdots & \vdots & \ddots \\ b_{n1} & a_{n2} & \dots & b_{nn} \\ \end{bmatrix}$$

Matrix Multiplication (2)

• $c_{ij}=\sum \limits_{1\leq k \leq n}^{}a_{ik}.b_{kj}$

Matrix Multiplication: Standard Algorithm

Running Time: $\Theta(n^3)$

for i=1 to n do
    for j=1 to n do
        C[i,j] = 0
        for k=1 to n do
            C[i,j] = C[i,j] + A[i,k] + B[k,j]
        endfor
    endfor
endfor

Matrix Multiplication: Divide & Conquer (1)

IDEA: Divide the $nxn$ matrix into $2x2$ matrix of $(n/2)x(n/2)$ submatrices.

Matrix Multiplication: Divide & Conquer (2)

$$\begin{bmatrix} c_{11} & c_{12} \\ c_{21} & c_{22} \end{bmatrix} = \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix} \cdot \begin{bmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end{bmatrix}$$

$$\text{8 mults and 4 adds of (n/2)*(n/2) submatrices}= \begin{cases} c_{11}=a_{11}b_{11}+a_{12}b_{21} \\ c_{21}=a_{21}b_{11}+a_{22}b_{21} \\ c_{12}=a_{11}b_{12}+a_{12}b_{22} \\ c_{22}=a_{21}b_{12}+a_{22}b_{22} \end{cases}$$

Matrix Multiplication: Divide & Conquer (3)

MATRIX-MULTIPLY(A, B)
    // Assuming that both A and B are nxn matrices
    if n == 1 then 
        return A * B
    else  
        //partition A, B, and C as shown before
        C[1,1] = MATRIX-MULTIPLY (A[1,1], B[1,1]) + 
                 MATRIX-MULTIPLY (A[1,2], B[2,1]); 

        C[1,2] = MATRIX-MULTIPLY (A[1,1], B[1,2]) + 
                MATRIX-MULTIPLY (A[1,2], B[2,2]); 

        C[2,1] = MATRIX-MULTIPLY (A[2,1], B[1,1]) + 
        MATRIX-MULTIPLY (A[2,2], B[2,1]);

        C[2,2] = MATRIX-MULTIPLY (A[2,1], B[1,2]) + 
        MATRIX-MULTIPLY (A[2,2], B[2,2]);
    endif      

    return C

Matrix Multiplication: Divide & Conquer Analysis

$T(n) = 8T(n/2) + \Theta(n^2)$

• $8$ recursive calls $\Longrightarrow 8T(\cdots)$
• each problem has size $n/2$ $\Longrightarrow \cdots T(n/2)$
• Submatrix addition $\Longrightarrow \Theta(n^2)$

Matrix Multiplication: Solving the Recurrence

• $T(n) = 8T(n/2) + \Theta(n^2)$

  • $a=8$, $b=2$
  • $f(n)=\Theta(n^2)$
  • $n^{log_b^a}=n^3$

• Case 1: $\frac{n^{log_b^a}}{f(n)}=\Omega(n^{\varepsilon}) \Longrightarrow T(n)=\Theta(n^{log_b^a})$

Similar with ordinary (iterative) algorithm.

Matrix Multiplication: Strassen’s Idea (1)

Compute $c_{11},c_{12},c_{21},c_{22}$ using $7$ recursive multiplications.

In normal case we need $8$ as below.

$$\begin{bmatrix} c_{11} & c_{12} \\ c_{21} & c_{22} \end{bmatrix} = \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix} \cdot \begin{bmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end{bmatrix}$$

$$\text{8 mults and 4 adds of (n/2)*(n/2) submatrices}= \begin{cases} c_{11}=a_{11}b_{11}+a_{12}b_{21} \\ c_{21}=a_{21}b_{11}+a_{22}b_{21} \\ c_{12}=a_{11}b_{12}+a_{12}b_{22} \\ c_{22}=a_{21}b_{12}+a_{22}b_{22} \end{cases}$$

Matrix Multiplication: Strassen’s Idea (2)

• Reminder:
  • Each submatrix is of size $(n/2)*(n/2)$
  • Each add/sub operation takes $\Theta(n^2)$ time
• Compute $P1 \dots P7$ using $7$ recursive calls to matrix-multiply

$$\begin{align*} P_1 & = a_{11} * (b_{12} - b_{22} ) \\ P_2 & = (a_{11} + a_{12} ) * b_{22} \\ P_3 & = (a_{21} + a_{22} ) * b_{11} \\ P_4 & = a_{22} * (b_{21} - b_{11} ) \\ P_5 & = (a_{11} + a_{22} ) * (b_{11} + b_{22} ) \\ P_6 & = (a_{12} - a_{22} ) * (b_{21} + b_{22} ) \\ P_7 & = ( a_{11} - a_{21} ) * (b_{11} + b_{12} ) \end{align*}$$

Matrix Multiplication: Strassen’s Idea (3)

$$\begin{align*} P_1 &= a_{11} * (b_{12} - b_{22} ) \\ P_2 &= (a_{11} + a_{12} ) * b_{22} \\ P_3 &= (a_{21} + a_{22} ) * b_{11} \\ P_4 &= a_{22} * (b_{21} - b_{11} ) \\ P_5 &= (a_{11} + a_{22} ) * (b_{11} + b_{22} ) \\ P_6 &= (a_{12} - a_{22} ) * (b_{21} + b_{22} ) \\ P_7 &= ( a_{11} - a_{21} ) * (b_{11} + b_{12} ) \end{align*}$$

• How to compute $c_{ij}$ using $P1 \dots P7$ ?

$$\begin{align*} c_{11} & = P_5 + P_4 – P_2 + P_6 \\ c_{12} & = P_1 + P_2 \\ c_{21} & = P_3 + P_4 \\ c_{22} & = P_5 + P_1 – P_3 – P_7 \end{align*}$$

Matrix Multiplication: Strassen’s Idea (4)

• $7$ recursive multiply calls
• $18$ add/sub operations

Matrix Multiplication: Strassen’s Idea (5)

e.g. Show that $c_{12} = P_1+P_2$ :

$$\begin{align*} c_{12} & = P_1 + P_2 \\ &= a_{11}(b_{12}–b_{22})+(a_{11}+a_{12})b_{22} \\ &= a_{11}b_{12}-a_{11}b_{22}+a_{11}b_{22}+a_{12}b_{22} \\ &= a_{11}b_{12}+a_{12}b_{22} \end{align*}$$

Strassen’s Algorithm

• Divide: Partition $A$ and $B$ into $(n/2)*(n/2)$ submatrices. Form terms to be multiplied using $+$ and $-$.

• Conquer: Perform $7$ multiplications of $(n/2)*(n/2)$ submatrices recursively.

• Combine: Form $C$ using $+$ and $–$ on $(n/2)*(n/2)$submatrices.

Recurrence: $T(n) = 7T(n/2) + \Theta(n^2)$

Strassen’s Algorithm: Solving the Recurrence (1)

• $T(n) = 7T(n/2) + \Theta(n^2)$

  • $a=7$, $b=2$
  • $f(n)=\Theta(n^2)$
  • $n^{log_b^a}=n^{lg7}$

• Case 1: $\frac{n^{log_b^a}}{f(n)}=\Omega(n^{\varepsilon}) \Longrightarrow T(n)=\Theta(n^{log_b^a})$

$T(n)=\Theta(n^{log_2^7})$

$2^3 = 8, 2^2=4$ so $\Longrightarrow log_2^7 \approx 2.81$

or use https://www.omnicalculator.com/math/log

Strassen’s Algorithm: Solving the Recurrence (2)

• The number $2.81$ may not seem much smaller than $3$

• But, it is significant because the difference is in the exponent.

• Strassen’s algorithm beats the ordinary algorithm on today’s machines for $n \geq 30$ or so.

• Best to date: $\Theta(n^{2.376 \dots})$ (of theoretical interest only)

Maximum Subarray Problem

Input: An array of values

Output: The contiguous subarray that has the largest sum of elements

• Input array:
  $[13][-3][-25][20][-3][-16][-23]\overbrace{[18][20][-7][12]}^{\textrm{max. contiguous subarray}}[-22][-4][7]$

Maximum Subarray Problem: Divide & Conquer (1)

• Basic idea:
  • Divide the input array into 2 from the middle
  • Pick the best solution among the following:
    • The max subarray of the left half
    • The max subarray of the right half
    • The max subarray crossing the mid-point

Maximum Subarray Problem: Divide & Conquer (2)

Maximum Subarray Problem: Divide & Conquer (3)

• Divide: Trivial (divide the array from the middle)

• Conquer: Recursively compute the max subarrays of the left and right halves

• Combine: Compute the max-subarray crossing the $mid-point$

  • (can be done in $\Theta(n)$ time).
  • Return the max among the following:
    • the max subarray of the $\text{left-subarray}$
    • the max subarray of the $\text{rightsubarray}$
    • the max subarray crossing the $\text{mid-point}$

TODO : detailed solution in textbook...

Conclusion : Divide & Conquer

• Divide and conquer is just one of several powerful techniques for algorithm design.
• Divide-and-conquer algorithms can be analyzed using recurrences and the master method (so practice this math).
• Can lead to more efficient algorithms

Quicksort (1)

• One of the most-used algorithms in practice
• Proposed by C.A.R. Hoare in 1962.
• Divide-and-conquer algorithm
• In-place algorithm
  • The additional space needed is O(1)
  • The sorted array is returned in the input array
  • Reminder: Insertion-sort is also an in-place algorithm, but Merge-Sort is not in-place.
• Very practical

Quicksort (2)

• Divide: Partition the array into 2 subarrays such that elements in the lower part $\leq$ elements in the higher part
• Conquer: Recursively sort 2 subarrays
• Combine: Trivial (because in-place)

Key: Linear-time $(\Theta(n))$ partitioning algorithm

Divide: Partition the array around a pivot element

• Choose a pivot element $x$

• Rearrange the array such that:

  • Left subarray: All elements $\leq x$
  • Right subarray: All elements $\geq x$

  

Conquer: Recursively Sort the Subarrays

Note: Everything in the left subarray ≤ everything in the right subarray

Note: Combine is trivial after conquer. Array already sorted.

Two partitioning algorithms

• Hoare’s algorithm:
  Partitions around the first element of subarray
  • $(pivot = x = A[p])$

• Lomuto’s algorithm:
  Partitions around the last element of subarray
  • $(pivot = x = A[r])$

Hoare’s Partitioning Algorithm (1)

• Choose a pivot element: $pivot = x = A[p]$

• Grow two regions:
  • from left to right: $A[p \dots i]$
  • from right to left: $A[j \dots r]$
    • such that:
  • every element in $A[p \dots i] \leq$ pivot
  • every element in $A[p \dots i] \geq$ pivot

Hoare’s Partitioning Algorithm (2)

Hoare’s Partitioning Algorithm (3)

• Elements are exchanged when
  • $A[i]$ is too large to belong to the left region
  • $A[j]$ is too small to belong to the right region
    • assuming that the inequality is strict
• The two regions $A[p \dots i]$ and $A[j \dots r]$ grow until $A[i] \geq pivot \geq A[j]$

  H-PARTITION(A, p, r)
        pivot = A[p]
          i = p - 1
          j = r - 1
          while true do
            repeat j = j - 1 until A[j] <= pivot
            repeat i = i - 1 until A[i] <= pivot
          if i < j then 
            exchange A[i] with A[j]
          else 
            return j

Hoare’s Partitioning Algorithm Example (Step-1)

Hoare’s Partitioning Algorithm Example (Step-2)

Hoare’s Partitioning Algorithm Example (Step-3)

Hoare’s Partitioning Algorithm Example (Step-4)

Hoare’s Partitioning Algorithm Example (Step-5)

Hoare’s Partitioning Algorithm Example (Step-6)

Hoare’s Partitioning Algorithm Example (Step-7)

Hoare’s Partitioning Algorithm Example (Step-8)

Hoare’s Partitioning Algorithm Example (Step-9)

Hoare’s Partitioning Algorithm Example (Step-10)

Hoare’s Partitioning Algorithm Example (Step-11)

Hoare’s Partitioning Algorithm Example (Step-12)

Hoare’s Partitioning Algorithm - Notes

• Elements are exchanged when
  • $A[i]$ is too large to belong to the left region
  • $A[j]$ is too small to belong to the right region
    • assuming that the inequality is strict
• The two regions $A[p \dots i]$ and $A[j \dots r]$ grow until $A[i] \geq pivot \geq A[j]$
• The asymptotic runtime of Hoare’s partitioning algorithm $\Theta(n)$

  H-PARTITION(A, p, r)
        pivot = A[p]
          i = p - 1
          j = r - 1
          while true do
            repeat j = j - 1 until A[j] <= pivot
            repeat i = i - 1 until A[i] <= pivot
          if i < j then exchange A[i] with A[j]
          else return j

Quicksort with Hoare’s Partitioning Algorithm

QUICKSORT (A, p, r)
  if p < r then
    q = H-PARTITION(A, p, r)
    QUICKSORT(A, p, q)
    QUICKSORT(A, q + 1, r)
  endif

Initial invocation: QUICKSORT(A,1,n)

Hoare’s Partitioning Algorithm: Pivot Selection

• if we select pivot to be $A[r]$ instead of $A[p]$ in H-PARTITION

• Consider the example where $A[r]$ is the largest element in the array:
  • End of H-PARTITION: $i = j = r$
  • In QUICKSORT: $q = r$
    • So, recursive call to:
      • QUICKSORT(A, p, q=r)
        • infinite loop

Correctness of Hoare’s Algorithm (1)

We need to prove $3$ claims to show correctness:

• Indices $i$ and $j$ never reference $A$ outside the interval $A[p \dots r]$
• Split is always non-trivial; i.e., $j \neq r$ at termination
• Every element in $A[p \dots j] \leq$ every element in $A[j+1 \dots r]$ at termination

Correctness of Hoare’s Algorithm (2)

• Notations:

  • $k$: $\#$ of times the while-loop iterates until termination
  • $i_m$: the value of index i at the end of iteration $m$
  • $j_m$: the value of index j at the end of iteration $m$
  • $x$: the value of the pivot element

• Note: We always have $i_1= p$ and $p \leq j_1 \leq r$
  because $x = A[p]$

Correctness of Hoare’s Algorithm (3)

Lemma 1: Either $i_k = j_k$ or $i_k = j_k+1$ at termination

Proof of Lemma 1:

• The algorithm terminates when $i \geq j$ (the else condition).

• So, it is sufficient to prove that $i_k – j_k \leq 1$

• There are $2$ cases to consider:

  • Case 1: $k = 1$, i.e. the algorithm terminates in a single iteration
  • Case 2: $k > 1$, i.e. the alg. does not terminate in a single iter.

  By contradiction, assume there is a run with $i_k – j_k > 1$

Correctness of Hoare’s Algorithm (4)

Original correctness claims:

• Indices $i$ and $j$ never reference A outside the interval $A[p \dots r]$
• Split is always non-trivial; i.e., $j \neq r$ at termination

Proof:

• For $k = 1$:
  • Trivial because $i_1 = j_1 = p$ (see Case 1 in proof of Lemma 2)
• For $k > 1$:
  • $i_k > p$ and $j_k < r$ (due to the repeat-until loops moving indices)
  • $i_k \leq r$ and $j_k \geq p$ (due to Lemma 1 and the statement above)

The proof of claims (a) and (b) complete

Correctness of Hoare’s Algorithm (5)

Lemma 2: At the end of iteration $m$, where $m<k$ (i.e. m is not the last iteration), we must have:
$A[p \dots i_m] \leq x$ and $A[j_m \dots r] \geq x$

Proof of Lemma 2:

• Base case: $m=1$ and $k>1$ (i.e. the alg. does not terminate in the first iter.)

Ind. Hyp.: At the end of iteration $m-1$, where $m<k$ (i.e. m is not the last iteration), we must have:
$A[p \dots i_m-1] \leq x$ and $A[j_m-1 \dots r] \geq x$

General case: The lemma holds for $m$, where $m < k$

Proof of base case complete!

Correctness of Hoare’s Algorithm (6)

Original correctness claim:

• (c) Every element in $A[ \dots j] \leq$ every element in $A[j+ \dots r]$ at termination

Proof of claim (c)

• There are $3$ cases to consider:
  • Case 1: $k=1$, i.e. the algorithm terminates in a single iteration
  • Case 2: $k>1$ and $i_k = j_k$
  • Case 3: $k>1$ and $i_k = j_k + 1$

Lomuto’s Partitioning Algorithm (1)

• Choose a pivot element: $pivot = x = A[r]$

• Grow two regions:
  • from left to right: $A[p \dots i]$
  • from left to right: $A[i+1 \dots j]$
    • such that:
      • every element in $A[p \dots i] \leq pivot$
      • every element in $A[i+1 \dots j] > pivot$

Lomuto’s Partitioning Algorithm (2)

Lomuto’s Partitioning Algorithm Ex. (Step-1)

Lomuto’s Partitioning Algorithm Ex. (Step-2)

Lomuto’s Partitioning Algorithm Ex. (Step-3)

Lomuto’s Partitioning Algorithm Ex. (Step-4)

Lomuto’s Partitioning Algorithm Ex. (Step-5)

Lomuto’s Partitioning Algorithm Ex. (Step-6)

Lomuto’s Partitioning Algorithm Ex. (Step-7)

Lomuto’s Partitioning Algorithm Ex. (Step-8)

Lomuto’s Partitioning Algorithm Ex. (Step-9)

Lomuto’s Partitioning Algorithm Ex. (Step-10)

Lomuto’s Partitioning Algorithm Ex. (Step-11)

Lomuto’s Partitioning Algorithm Ex. (Step-12)

Lomuto’s Partitioning Algorithm Ex. (Step-13)

Lomuto’s Partitioning Algorithm Ex. (Step-14)

Lomuto’s Partitioning Algorithm Ex. (Step-15)

Quicksort with Lomuto’s Partitioning Algorithm

QUICKSORT (A, p, r)
  if p < r then
    q = L-PARTITION(A, p, r)
    QUICKSORT(A, p, q - 1)
    QUICKSORT(A, q + 1, r)
  endif

Initial invocation: QUICKSORT(A,1,n)

Comparison of Hoare’s & Lomuto’s Algorithms (1)

• Notation: $n=r-p+1$
  • $pivot=A[p]$ (Hoare)
  • $pivot=A[r]$ (Lomuto)
• $\#$ of element exchanges: $e(n)$
  • Hoare: $0 \geq e(n) \geq \lfloor \frac{n}{2} \rfloor$
    • Best: $k=1$ with $i_1=j_1=p$ (i.e., $A[p+1 \dots r]>pivot$)
    • Worst: $A[p+1 \dots p+ \lfloor \frac{n}{2} \rfloor - 1] \geq pivot \geq A[p+ \lceil \frac{n}{2} \rceil \dots r]$
  • Lomuto : $1 \leq e(n) \leq n$
    • Best: $A[p \dots r -1]>pivot$
    • Worst: $A[p \dots r-1] \leq pivot$

Comparison of Hoare’s & Lomuto’s Algorithms (2)

• $\#$ of element comparisons: $c_e(n)$

  • Hoare: $n+1 \leq c_e(n) \leq n+2$
    • Best: $i_k=j_k$
    • Worst: $i_k=j_k+1$
  • Lomuto: $c_e(n)=n-1$

• $\#$ of index comparisons: $c_i(n)$

  • Hoare: $1 \leq c_i(n) \leq \lfloor \frac{n}{2} \rfloor + 1 | (c_i(n)=e(n)+1)$
  • Lomuto: $c_i(n)=n-1$

Comparison of Hoare’s & Lomuto’s Algorithms (3)

• $\#$ of index increment/decrement operations: $a(n)$

  • Hoare: $n+1 \leq a(n) \leq n+2 | (a(n)=c_e(n))$
  • Lomuto: $n \leq a(n) \leq 2n-1 | (a(n)=e(n)+(n-1))$

• Hoare’s algorithm is in general faster

• Hoare behaves better when pivot is repeated in $A[p \dots r]$

  • Hoare: Evenly distributes them between left & right regions
  • Lomuto: Puts all of them to the left region

Analysis of Quicksort (1)

QUICKSORT (A, p, r)
  if p < r then
    q = H-PARTITION(A, p, r)
    QUICKSORT(A, p, q)
    QUICKSORT(A, q + 1, r)
  endif

Initial invocation: QUICKSORT(A,1,n)

Assume all elements are distinct in the following analysis

Analysis of Quicksort (2)

• H-PARTITION always chooses $A[p]$ (the first element) as the pivot.
• The runtime of QUICKSORT on an already-sorted array is $\Theta(n^2)$

Example: An Already Sorted Array

Partitioning always leads to $2$ parts of size $1$ and $n-1$

Worst Case Analysis of Quicksort

• Worst case is when the PARTITION algorithm always returns imbalanced partitions (of size $1$ and $n-1$) in every recursive call.
  • This happens when the pivot is selected to be either the min or max element.
  • This happens for H-PARTITION when the input array is already sorted or reverse sorted

$$\begin{align*} T(n) &= T(1) + T(n-1) + Θ(n) \\ &= T(n-1) + Θ(n) \\ &= Θ(n2) \end{align*}$$

Worst Case Recursion Tree

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

Best Case Analysis (for intuition only)

• If we’re extremely lucky, H-PARTITION splits the array evenly at every recursive call

$$\begin{align*} T(n) &= 2T(n/2) + \Theta(n) \\ &= \Theta(nlgn) \end{align*}$$

(same as merge sort)

• Instead of splitting $0.5:0.5$, if we split $0.1:0.9$ then we need solve following equation.

$$\begin{align*} T(n) &= T(n/10) + T(9n/10) + \Theta(n) \\ &= \Theta(nlgn) \end{align*}$$

“Almost-Best” Case Analysis

Balanced Partitioning (1)

• We have seen that if H-PARTITION always splits the array with $0.1-to-0.9$ ratio, the runtime will be $\Theta(nlgn)$.

• Same is true with a split ratio of $0.01-to-0.99$, etc.

• Possible to show that if the split has always constant $(\Theta(1))$ proportionality, then the runtime will be $\Theta(nlgn)$.

• In other words, for a constant $\alpha | (0 < \alpha ≤ 0.5)$:

  • $\alpha–to–(1-\alpha)$ proportional split yields $\Theta(nlgn)$ total runtime

Balanced Partitioning (2)

• In the rest of the analysis, assume that all input permutations are equally likely.
  • This is only to gain some intuition
  • We cannot make this assumption for average case analysis
  • We will revisit this assumption later
• Also, assume that all input elements are distinct.

Balanced Partitioning (3)

• Question: What is the probability that H-PARTITION returns a split that is more balanced than $0.1-to-0.9$?

Balanced Partitioning (4)

Reminder: H-PARTITION will place the pivot in the right partition unless the pivot is the smallest element in the arrays.

Question: If the pivot selected is the mth smallest value $(1 < m ≤ n)$ in the input array, what is the size of the left region after partitioning?

Balanced Partitioning (5)

• Question: What is the probability that the pivot selected is the $m^{th}$ smallest value in the array of size $n$?

  • $1/n$ (since all input permutations are equally likely)

• Question: What is the probability that the left partition returned by H-PARTITION has size $m$, where $1<m<n$?

  • $1/n$ (due to the answers to the previous 2 questions)

Balanced Partitioning (6)

• Question: What is the probability that H-PARTITION returns a split that is more balanced than $0.1-to-0.9$?

$$\begin{align*} Probability &=\sum \limits_{q=0.1n+1}^{0.9n-1}\frac{1}{n} \\ &=\frac{1}{n}(0.9n-1-0.1n-1+1) \\ &= 0.8-\frac{1}{n} \\ & \approx 0.8 \text{ for large n} \end{align*}$$

Balanced Partitioning (7)

• The probability that H-PARTITION yields a split that is more balanced than $0.1-to-0.9$ is $80\%$ on a random array.

• Let $P_{\alpha>}$ be the probability that H-PARTITION yields a split more balanced than $\alpha-to-(1-\alpha)$, where $0 < \alpha \leq 0.5$

• Repeat the analysis to generalize the previous result

Balanced Partitioning (8)

• Question: What is the probability that H-PARTITION returns a split that is more balanced than $\alpha-to-(1-\alpha)$?

$$\begin{align*} Probability & =\sum \limits_{q=\alpha n+1}^{(1-\alpha)n-1}\frac{1}{n} \\ & =\frac{1}{n}((1-\alpha)n-1- \alpha n-1+1) \\ & = (1-2\alpha)-\frac{1}{n} \\ & \approx (1-2\alpha) \text{ for large n} \end{align*}$$

Balanced Partitioning (9)

• We found $P_{\alpha >}=1-2\alpha$
  • Ex: $P_{0.1>}=0.8$ and $P_{0.01>}=0.98$
• Hence, H-PARTITION produces a split
  • more balanced than a
    • $0.1-to-0.9$ split $80\%$ of the time
    • $0.01-to-0.99$ split $98\%$ of the time
  • less balanced than a
    • $0.1-to-0.9$ split $20\%$ of the time
    • $0.01-to-0.99$ split $2\%$ of the time

Intuition for the Average Case (1)

• Assumption: All permutations are equally likely

  • Only for intuition; we’ll revisit this assumption later

• Unlikely: Splits always the same way at every level

• Expectation:

  • Some splits will be reasonably balanced
  • Some splits will be fairly unbalanced

• Average case: A mix of good and bad splits

  • Good and bad splits distributed randomly thru the tree

Intuition for the Average Case (2)

• Assume for intuition: Good and bad splits occur in the alternate levels of the tree
  • Good split: Best case split
  • Bad split: Worst case split

Intuition for the Average Case (3)

Compare 2-successive levels of avg case vs. 1 level of best case

Intuition for the Average Case (4)

• In terms of the remaining subproblems, two levels of avg case is slightly better than the single level of the best case

• The avg case has extra divide cost of $\Theta(n)$ at alternate levels

• The extra divide cost $\Theta(n)$ of bad splits absorbed into the $\Theta(n)$ of good splits.

• Running time is still $\Theta(nlgn)$

  • But, slightly larger hidden constants, because the height of the recursion tree is about twice of that of best case.

Intuition for the Average Case (5)

• Another way of looking at it:

  • Suppose we alternate lucky, unlucky, lucky, unlucky, $\dots$
  • We can write the recurrence as:
    • $L(n) = 2U(n/2) + \Theta(n)$ lucky split (best)
    • $U(n) = L(n-1) + \Theta(n)$ unlucky split (worst)
  • Solving:

  $$\begin{align*} L(n) & = 2(L(n/2-1) + \Theta(n/2)) + \Theta(n) \\ & = 2L(n/2-1) + \Theta(n) \\ & = Θ(nlgn) \end{align*}$$

• How can we make sure we are usually lucky for all inputs?

Summary: Quicksort Runtime Analysis (1)

• Worst case: Unbalanced split at every recursive call

$$\begin{align*} T(n) & = T(1) + T(n-1) + \Theta(n) \\ T(n) & = \Theta(n2) \end{align*}$$

• Best case: Balanced split at every recursive call (extremely lucky)

$$\begin{align*} T(n) & = 2T(n/2) + \Theta(n) \\ T(n) & = \Theta(nlgn) \end{align*}$$

Summary: Quicksort Runtime Analysis (2)

• Almost-best case: Almost-balanced split at every recursive call

$$\begin{align*} T(n) &=T(n/10)+T(9n/10)+ \Theta(n) \\ \text{or } T(n) &= T(n/100) + T(99n/100) + Θ(n) \\ \text{or } T(n) &= T(\alpha n) + T((1-\alpha n)+ \Theta(n) \end{align*}$$

for any constant $\alpha, 0 < \alpha \leq 0.5$

Summary: Quicksort Runtime Analysis (3)

• For a random input array, the probability of having a split

  • more balanced than $0.1 – to – 0.9 : 80\%$
  • more balanced than $0.01 – to – 0.99 : 98\%$
  • more balanced than $\alpha – to – (1-\alpha) : 1 – 2 \alpha$

• for any constant $\alpha, 0 < \alpha \leq 0.5$

Summary: Quicksort Runtime Analysis (4)

• Avg case intuition: Different splits expected at different levels

  • some balanced (good), some unbalanced (bad)

• Avg case intuition: Assume the good and bad splits alternate

  • i.e. good split -> bad split -> good split -> …
  • $T(n) = \Theta(nlgn)$
    • (informal analysis for intuition)

Randomized Quicksort

• In the avg-case analysis, we assumed that all permutations of the input array are equally likely.
  • But, this assumption does not always hold
  • e.g. What if all the input arrays are reverse sorted?
    • Always worst-case behavior
• Ideally, the avg-case runtime should be independent of the input permutation.
• Randomness should be within the algorithm, not based on the distribution of the inputs.
  • i.e. The avg case should hold for all possible inputs

Randomized Algorithms (1)

• Alternative to assuming a uniform distribution:
  • Impose a uniform distribution
  • e.g. Choose a random pivot rather than the first element
• Typically useful when:
  • there are many ways that an algorithm can proceed
  • but, it’s difficult to determine a way that is always guaranteed to be good.
  • If there are many good alternatives; simply choose one randomly.

Randomized Algorithms (1)

• Ideally:
  • Runtime should be independent of the specific inputs
  • No specific input should cause worst-case behavior
  • Worst-case should be determined only by output of a random number generator.

Randomized Quicksort (1)

• Using Hoare’s partitioning algorithm:

R-QUICKSORT(A, p, r)
  if p < r then
    q = R-PARTITION(A, p, r)
    R-QUICKSORT(A, p, q)
    R-QUICKSORT(A, q+1, r)

R-PARTITION(A, p, r)
  s = RANDOM(p, r)
  exchange A[p] with A[s]
  return H-PARTITION(A, p, r)

• Alternatively, permuting the whole array would also work
  • but, would be more difficult to analyze

Randomized Quicksort (2)

• Using Lomuto’s partitioning algorithm:

R-QUICKSORT(A, p, r)
  if p < r then
    q = R-PARTITION(A, p, r)
    R-QUICKSORT(A, p, q-1)
    R-QUICKSORT(A, q+1, r)

R-PARTITION(A, p, r)
  s = RANDOM(p, r)
  exchange A[r] with A[s]
  return L-PARTITION(A, p, r)

• Alternatively, permuting the whole array would also work
  • but, would be more difficult to analyze

Notations for Formal Analysis

• Assume all elements in $A[p \dots r]$ are distinct

  • Let $n = r – p + 1$

• Let $rank(x) = |{A[i]: p \leq i \leq r \text{ and } A[i] \leq x}|$

• i.e. $rank(x)$ is the number of array elements with value less than or equal to $x$

  • $A=\{5,9,7,6,8,1,4\}$
  • $p=5,r=4$
  • $rank(5)=3$
    • i.e. it is the $3^{rd}$ smallest element in the array

Formal Analysis for Average Case

• The following analysis will be for Quicksort using Hoare’s partitioning algorithm.

• Reminder: The pivot is selected randomly and exchanged with $A[p]$ before calling H-PARTITION

• Let $x$ be the random pivot chosen.

• What is the probability that $rank(x) = i$ for $i = 1, 2, \dots n$ ?

  • $P(rank(x) = i) = 1/n$

Various Outcomes of H-PARTITION (1)

• Assume that $rank(x)=1$
  • i.e. the random pivot chosen is the smallest element
  • What will be the size of the left partition $(|L|)$?
  • Reminder: Only the elements less than or equal to $x$ will be in the left partition.

$A=\{\overbrace{2}^{p=x=pivot}\underbrace{,}_{\Longrightarrow|L|=1 } 9,7,6,8,5,\overbrace{4}^r\}$

$p=2,r=4$
$pivot=x=2$

TODO: convert to image...S6_P9

Various Outcomes of H-PARTITION (2)

• Assume that $rank(x)>1$
  • i.e. the random pivot chosen is not the smallest element
  • What will be the size of the left partition $(|L|)$?
  • Reminder: Only the elements less than or equal to $x$ will be in the left partition.
  • Reminder: The pivot will stay in the right region after H-PARTITION if $rank(x)>1$

$A=\{\overbrace{2}^{p}, 4 \underbrace{,}_{\Longrightarrow|L|=rank(x)-1}7,6,8,\overbrace{5,}^{pivot}\overbrace{9}^r\}$

$p=2,r=4$
$pivot=x=5$

TODO: convert to image...S6_P10

Various Outcomes of H-PARTITION - Summary (1)

• $x: pivot$

• $|L|: \text{size of left region}$

• $P(rank(x) = i) = 1/n \text{ for } 1 \leq i \leq n$

  • $\text{if } rank(x) = 1 \text{ then } |L| = 1$
  • $\text{if } rank(x) > 1 \text{ then } |L| = rank(x) - 1$

• $P(|L| = 1) = P(rank(x) = 1) + P(rank(x) = 2)$

  • $P(|L| = 1) = 2/n$

• $P(|L| = i) = P(rank(x) = i+1) \text{ for } 1< i < n$

  • $P(|L| = i) = 1/n \text{ for } 1< i < n$

Various Outcomes of H-PARTITION - Summary (2)

Average - Case Analysis: Recurrence (1)

$x=pivot$

$$\begin{align*} T(n) & = \frac{1}{n}(T(1)+t(n-1) ) & rank:1 \\ & + \frac{1}{n}(T(1)+t(n-1) ) & rank:2 \\ & + \frac{1}{n}(T(2)+t(n-2) ) & rank:3 \\ & \vdots & \vdots \\ & + \frac{1}{n}(T(i)+t(n-i) ) & rank:i+1 \\ & \vdots & \vdots \\ & + \frac{1}{n}(T(n-1)+t(1) ) & rank:n \\ & + \Theta(n) \end{align*}$$

Average - Case Analysis: Recurrence (2)

$$\begin{align*} T(n) &= \frac{1}{n}\sum \limits_{q=1}^{n-1}(T(q)+T(n-q))+\frac{1}{n}(T(1)+T(n-1))+\Theta(n)\\ & \text{Note: } \frac{1}{n}(T(1)+T(n-1))=\frac{1}{n}(\Theta(1)+O(n^2))=O(n) \\ T(n) &= \frac{1}{n}\sum \limits_{q=1}^{n-1}(T(q)+T(n-q))+\Theta(n) \end{align*}$$