Recall the QuickSelect algorithm done in class, where the pivot is chosen uniformly at random from the elements of the vector. The goal of this question is to understand how robust this method of choosing the pivot is$.$

Consider a variant of the algorithm, which works the same way, except that for any input vector $$\backslash$vec$\{$x$\}=($x$\_1,\backslash$ldots$,$ x$\_$n$)$$$,$ element $x$\_$i$ is chosen to be the pivot with probability proportional to $$1-1/($n$+$i$)^3$$$.$ More precisely, the probability is

$$

$\backslash$frac$\{1-1/($n$+$i$)^3\}\{\backslash$sum$\_\{$k$=1\}^$n $\backslash$left$[1-1/($n$+$k$)^3\backslash$right$]\}\backslash ,.$

$$

Can you still show an upper bound of $O$($n$)$$ comparisons in expectation for this variant of QuickSelect? Justify your answers. If you answered yes, then include the proof showing the upper bound for the expected number of comparisons made by this version of the algorithm.