263 Lecture 3

QuickSort(A):
	Pivot = A[0]
	Left = all of A[1...n-1] smaller than Pivot
	Right = Rest of A [1...n-1]
	return [QuickSort(Left)], Pivot, QuickSort(Right)]
        

# Comparisons ≤ # Pairs = (n 2) = n(n-1)/2 \in O(n^2) \in \Theta(n^2)

Assume 0.1 on left and 0.9 on right.

        	h = height
        	1 = (0.9)^h * n
        	h = log_(k/9) n
        

Show average # compparisons is O(nlogn)

x <- random var = # comparisons

E[x] = ∑ P_1(x = x_i) * x_i

x_i \in supp(x)

E(x) = ∑ t(I) / |U| where I \in U(Inputs of size n)

X = ∑_(i=1) ∑_(j = i + 1) E(X_i_j) 2/(j-i+1) = ∑ 2(1/2 + 1/3 + ... + 1/(n-i+1)) ≤ 2nlogn \in O(nlogn)

Pr(X_i_j = 1) = 2/(j-i+1)