Randomized Algorithms and Quicksort

# Randomized Algorithms #

Idea: make random choices during the algorithm

• Hope the algorithm works
• Hope the algorithm is fast

Today: look at algorithms that always work and are probably fast

• e.g. `select` with random pivot

## Analysis of randomized algorithms #

Scenario 1: publish algorithm, adversarially picked input, run algorithm (expected running time - as a random variable)

Scenario 2: publish algorithm, adversarially picked input and randomness (worst-case analysis)

### Bogosort #

Algorithm `BogoSort(A)`:

• While true:
• Randomly permute A (O(n) via Knuth shuffle)
• Check if A is sorted
• If A is sorted, return A

Analysis:

• Let xi be 1 if A is sorted after iteration i and 0 otherwise
• E[xi] = 1/n! (n! permutations, and only one of them is sorted)
• E[number of iterations until A is sorted] = n!
• Expected running time of Bogosort:
• E[running time on a list of length n] = E[number of iterations * time per iteration] = (time per iteration)E[number of iterations] = O(n * n!)
• Worst case runtime: infinite!

### Quicksort #

Algorithm `QuickSort(A)`:

• If len(A) <= 1: return
• Pick some x = A[i] at random; let x be the pivot
• Partition the rest of A into
• L (less than x)
• R (greater than x)
• Rearrange A into with [L, x, R]
• QuickSort(L)
• QuickSort(R)

Analysis:

• T(n) = T(|L|) + T(|R|) + O(n)
• Ideally, if the pivot splits the array exactly in half:
• T(n) = 2T(n/2) + O(n)
• T(n) = O(n log n)
• What happens in average/worst case?

Theorem: the expected running time of quicksort is O(n log n)

Proof: count the number of comparisons made by the algorithm (see lecture slides)