Analysis(continued) To obtain an upper bound, assume that the ith element al ways falls in the larger side of the partition T(max(0, n-1)+o(n) if0: n-1 split T(max1, n-2))+o(n) if 1: n-2 split T(max(n-1,0)+o(n ifn-1: 0 split 2X(T(maxk, n-k-1)+0(n) k=0 o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.7© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.7 Analysis (continued) T(n) = T(max{0, n–1}) + Θ(n) if 0 : n–1 split, T(max{1, n–2}) + Θ(n) if 1 : n–2 split, M T(max{n–1, 0}) + Θ(n) if n–1 : 0 split, ∑ ( ) − = = − − + Θ 1 0 (max{ , 1}) ( ) n k Xk T k n k n . To obtain an upper bound, assume that the ith element always falls in the larger side of the partition: