Expected tree height But, average node depth of a randomly built BST=O(g n) does not necessarily mean that its expected height is also O(g n)(although it is) Example ≤1gn Ave.deph≤1nlgn+nn O(gn) c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.5© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.5 Expected tree height But, average node depth of a randomly built BST = O(lg n) does not necessarily mean that its expected height is also O(lg n) (although it is). Example. ≤ lg n h = n (lg ) 2 lg 1 O n n n n n n =   ⋅ Ave. depth ≤ ⋅ +