Consider the following algorithm given in Java code:

$1.$ public class Sort $\{$

$2.$ public static void sort$($int$[]$ array, int low, int high$)\{$

$3.$ if $($low $<$ high$)\{$

$4.//$ Find pivot element such that element smaller than pivot are on the left

$5.//$ Element greater than pivot are on the right

$6.$ int pivotIndex $=$ partition$($array$,$ low, high$)$;

$7.//$ Recursively sort elements before and after partition

$8.$ sort$($array$,$ low, pivotIndex $-1)$;

$9.$ sort$($array$,$ pivotIndex $+1,$ high$)$;

$10.\}$

$11.\}$

$12.$

$13.$ private static int partition$($int$[]$ array, int low, int high$)\{$

$14.$ int pivot $=$ array$[$high$]$;

$15.$ int i $=($low $-1)$;

$16.$ for $($int j $=$ low; j $<$ high; j$++)\{$

$17.$ if $($array$[$j$]<=$ pivot$)\{$

$18.$ i$++$;

$19.$ int temp $=$ array$[$i$]$;

$20.$ array$[$i$]=$ array$[$j$]$;

$21.$ array$[$j$]=$ temp;

$22.\}$

$23.\}$

$24.$ int temp $=$ array$[$i $+1]$;

$25.$ array$[$i $+1]=$ array$[$high$]$;

$26.$ array$[$high$]=$ temp;

$27.$ return i $+1$;

$28.\}$

$29.\}$

Note: Always give the tightest upper bound possible when giving the Big$-$O$.$ For example, if you can

prove that $()$ is $(),$ and that $()$ is $("),$ only choose the tighter upper bound, i$.$e$.()$ is $().$

a$)[10$ pts$]$ Give a Big$-$O $()$ for the worst$-$case running time of this algorithm for an input array of

length $.$ Explain how you obtained this worst case.

b$)[10$ pts$]$ Give a Big$-$Omega $()$ for the best$-$case running time of this algorithm for an input

array of length $.$ Explain the type of inputs $($sample inputs$)$ that will produce this best case.