Height of a randomly built binary search tree Outline of the analysis: Prove jensen’ s inequali的, which says that feDs(XI for any convex function fand random variable x Analyze the exponential height of a randomly built bst on n nodes which is the random variable y= 2An where X is the random variable denoting the height of the bst Prove that 2ELAnl EJ2Xn1=E[Ym =O(n) and hence that EXn=O(g n) c 2001 by Charles E Leiserson Introduction to Algorithms Day 17 L9.6
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.6 Height of a randomly built binary search tree • Prove Jensen’s inequality, which says that f(E[X]) ≤ E[f(X)] for any convex function f and random variable X. • Analyze the exponential height of a randomly built BST on n nodes, which is the random variable Yn = 2Xn, where Xn is the random variable denoting the height of the BST. • Prove that 2E[Xn] ≤ E[2Xn ] = E[Yn] = O(n3), and hence that E[Xn] = O(lg n). Outline of the analysis:
Convex functions A functionf:R>R is convex if for all a,B≥0 such that a+β=1, we have fax+阝y)≤o(x)+B/f orax,y∈ R f afx)+ B) f fax+阝y) x ax+ B c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.7
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.7 Convex functions A function f : R → R is convex if for all α,β ≥ 0 such that α + β = 1, we have f(αx + βy) ≤ αf(x) + βf(y) for all x,y ∈ R. αx + βy αf(x) + βf(y) f(αx + βy) x y f(x) f(y) f
Convexity lemma Lemma Let f: R>R be a convex function an nd let (ap,a2,.,an) be a set of nonnegative constants such that 2la= 1. Then, for any set x,x2,.,xn) of real numbers, we have ∑axk|s∑a/(x) k=1 k=1 Proof By induction on n. For n=1, we have I=l, and hence fax,sav( trivially c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.8
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.8 Convexity lemma Lemma. Let f : R → R be a convex function, and let {α1, α2 , …, αn} be a set of nonnegative constants such that ∑k αk = 1. Then, for any set {x1, x2, …, xn} of real numbers, we have ( ) 1 1 ∑ ∑ = = ≤ nk k k nk k k f α x α f x Proof. By induction on n. For n = 1, we have α1 = 1, and hence f(α1x1) ≤ α1f(x1) trivially.
Proof (continued) Inductive step kkk= n-n +(1 k X k=1 k n algebra c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.9
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.9 Proof (continued) − = + − ∑ ∑− = =1 1 11 (1 )nk k n k n n n nk k k f x f x x α α α α α Inductive step: Algebra
Proof (continued) Inductive step k k k anIn+(l-a n n k=1 ≤an(x)+(-an)∑,“xk k=1 Convexity c 2001 by Charles E Leiserson Introduction to Agorithms Day17L9.10
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.10 Proof (continued) − ≤ + − − = + − ∑ ∑ ∑ − = − = = 1 1 1 1 1 1 ( ) (1 ) 1 (1 ) n k k n k n n n n k k n k n n n n k k k f x f x f x f x x α α α α α α α α α Inductive step: Convexity