Question: For an array with n elements, what is the maximum number of swaps that the algorithm outlined in the last question's hint will perform during a pivot operation? Do not use big-O or Theta notation.
Answer: We initially perform a swap. In the worst case, every time we will not step l up any and we will not step r up any; then in each iteration l increments by one and r decrements by one, and one swap is performed. After (n-1)/2 iterations we will have l==r, and the loop will end. Then we perform one swap at the end. The total number of swaps, then, is 1 + (n-1)/2 + 1 = (n + 3) / 2.