The QuickFind algorithm. The input is an array A$[1$ : n$]$ of distinct numbers and an integer k$,1<=$ k $<=$ n$.$ The task is to find the kth smallest number in A$.$ Recursive subproblems concern subarrays A$[$i : j$],$ and one is seeking the hth smallest item in A$[$i : j$].$ The initial call is to QuickFind$($A$,1,$ n$,$ k$).$ If i $=$ j the algorithm simply returns A$[$i$].$ Otherwise it applies the Partition algorithm from Quicksort, and either returns the pivot item if it is the hth smallest item, or recurses on the left subarray if it contains at least h items $($i$.$e$.$ if h $>=$ j $$ i $+1),$ and otherwise recurses on the right subarray $($but with h replaced by h $($l $$ i $+1),$ the reduction in the size of the subproblem$).$

Pseudo$-$code follows.

procedure QuickFind$($A$,$ i$,$ j$,$ h$)$

$(*$ Finds the kth smallest item in A$[$i : j$]*)$ if j $=$ i then return $($A$[$i$])$

else

Partition$($A$,$ i$,$ j$,$ l$)$;

$(*$ l in the index of the pivot location after the partition completes $*)$ if h$=$l$$i$+1$thenreturn$($A$[$l$])$

else

if h l $$ i $+1*)$ QuickFind $($A$,$ l $+1,$ j$,$ h $$ l $+$ i $1)$ end if

end if end if

end procedure

Given this algorithm, I am looking to solve this problem:

Recall the QuickFind algorithm from homework $2.$ Show that with probability at least $1/$n it takes time $\backslash$Omega $($n log n$/$ log log n$).$

Hint. Suppose you are seeking the smallest item, and also that each of the first log n$/$ log log n partitions is among the top log log n$/$ log n fraction of the remaining items.

What is the minimum size of the resulting subproblem after log n$/$ log log n iterations? $($i$.$e$.$ you need to show a bound b such that the resulting subproblem has size at least b$.)$

Give a lower bound on the probability of this event.

Give a lower bound on the runtime to reach this point.

You may assume $(11/$x$)$x $>=1/(2$e$)$ for x $>=3.$

Also, it may be helpful to recall that log n $=2$log log n$.$

Finally, note that it suffices to show a lower bound for all n $>=$ n$,$ where n is a suitable constant.