Question $2$

QuickSort requires manipulating an array so that one element can be used as a pivot. Interestingly,

some elements can be used as pivots without changing the array. Design an algorithm that, given

an array, returns a list of valid pivots in widetilde$(O)(n)$ time and prove its correctness.

Note: widetilde$(O)(n)$ is called soft$-O.$ A function $f(n)$ is widetilde$(O)(g(n))$ if $f(n)inOg(n)lo{g}_k^k(n)$ for some $k.$ That is$,$

$f(n)$ is $O(g(n))$ after ignoring $log$ factors.