Sorting Quicksort Quicksort Lemma(7.1) Let X be the number of comparisons performed in line 4 of PARTITION over the entire execution of QUICKSORT on an n-element array.Then the running time of QUICKSORT is O(n+X). Proof. By the discussion above,the algorithm makes at most n calls to PARTITION,each of which does a constant amount of work and then executes the for loop some number of times.Each iteration of the for loop executes line 4. 發 MA Jun (Institute of Computer Software) Problem Solving Api23.2020 11/40Sorting Quicksort Quicksort Lemma (7.1) Let X be the number of comparisons performed in line 4 of Partition over the entire execution of Quicksort on an n-element array. Then the running time of Quicksort is O(n + X). Proof. By the discussion above, the algorithm makes at most n calls to Partition, each of which does a constant amount of work and then executes the for loop some number of times. Each iteration of the for loop executes line 4. MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 11 / 40