Node depth The depth of a node the number of comparisons made during TREE-INSERT. Assuming all input permutations are equally likely, we have Average node depth E∑( comparisons to insert no lO(nlgn) (quicksort analysis O(gn) c 2001 by Charles E Leiserson Introduction to Agorithms Day 17 L9.4© 2001 by Charles E. Leiserson Introduction to Algorithms Day 17 L9.4 Node depth The depth of a node = the number of comparisons made during TREE-INSERT. Assuming all input permutations are equally likely, we have ( ) (lg ) ( lg ) 1 #comparisons to insert node 1 1 O n O n n n E i n n i = =   = ∑= Average node depth . (quicksort analysis)