How many element movements does Quicksort do on the average? (Give a formula based on n, the size of the array -- an exact formula is not needed; you may use big-O notation for your answer). Note1: The book discusses several versions of Quicksort; for this problem, assume we are analyzing Algorithm 4.2 (Page 159/160)

Note2: For this analysis, you may assume all the elements in the array are distinct, and that all initial permutations of the elements are equally likely. Under these conditions, the answer to the following question should be obvious: When an element is compared with the pivot, what is the probability that it has to be moved?

Algorithm 4.2 Quicksort Input: Array E and indexes first, and last, such that elements Elil are defined for firsts i last. Outpui Elfirst],..., Ellast] is a sorted rearrangement of the same elements. 160 Chapter 4 Sorting firs lasi pivot partition first splitPoint last