$(5$ points$)$ It seems Mr E has just learned about quicksort, something he didn't seem

interested in before $($you suspect he might be reading your old homework$).$ He over$-$

heard a lecture on heaps, and now he claims to have a "really important breakthrough"

regarding quicksort's pivot selection. He suggests the following algorithm:

Heapify the array $a.$

Choose a leaf element at random $($i$.$e$,$ an element in $A[|$~$\frac{n}{2}])$ and use it as

a pivot.

Apply Lomuto's partitioning.

If this scheme is used in quicksort, what is the worst case complexity of the resulting

algorithm?Choose a leaf element at random $($i$.$e$,$ an element in A$[2$n$],...,$ A$[$n$])$ and use it as a pivot.