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: