Position of Pivot Left of pivot Right of pivot T(n left ) T(n right ) 1 0 n-1 T(0) T(n-1) 2 1 n-2 T(1) T(n-2) 3 2 n-2 T(2) T(n-3) --- --- --- --- -- --- --- --- --- --- --- --- --- --- --- n-2 n-3 2 T(n-3) T(2) n-1 n-2 1 T(n-1) T(1) n n-1 0 T(n-1) T(0) The number of comparisons for first call on partion: Assume left_to_right moves over k smaller element and thus k comparisons. So when right_to_left crosses left_to_right it has made n-k+1 comparisons. So first call on partition makes n+1 comparisons. The average case complexity of quicksort is: {T(n) = comparisons for first call on quicksort + Σ 1<=nleft,nright<=n [T(n left )+T(n right )]} =(n+1) + 2[T(0) + T(1) + T(2) + ----T(n-1)/n.....(1) So, nT(n) = n(n+1) + 2[T(0) + T(1) + T(2) + --- +T(n-2) + T(n-1)] .......(2) (n-1)T(
Instead of hoping the incremental construction yields a shallow tree, we can construct the tree that minimizes the search time. We consider the common problem in which items have different probabilities to be the target of a search. For example,some words in the English dictionary are more commonly searched than others and are therefore assigned a higher probability. Let a 1 < a 2 < . . . < a n be the items and p i is the corresponding probabilities. To simplify the discussion, we only consider successful searches and thus assume n Σ i=1   p i = 1 . The expected number of comparisons for a successful search in a binary search tree T storing the n item is 1+ C(T) = n Σ i=1   p i .(δ i + 1) = 1 + n Σ i=1   p i .δ i , where δ i is the depth of the node that stores a i . C(T ) is the weighted path length or the cost of T . We study the problem of constructing a tree that minimizes th