Specify the steps of your algorithm. You don$$t have to formally prove your

algorithm is correct, but it would be a good idea for you to do so using strong mathe$-$

matical induction $($it would be good practice$).$

Your algorithm must:

$1.$ be a valid divide and conquer algorithm, where each recursive call processes a sub

list whose size is roughly half that of the given sub list,

$2.$ return a valid popular element in the given input list for any valid input list,

$3.$ use O$(1)$ additional space, not counting the implicit space used by the call stack

$($so$,$ just local variables, and no extra auxiliary data structures of any kind$),$

$4.$ not modify the given input list,

$5.$ not use any repetition $($loop$)$ structures, and

$6.$ have best case running time O$(1).$

You may assume that Count $($x$,$ A $=[$al$,$ al$+1,...,$ ar$])$ returns the number of occurrences

of x in A and its worst case running time is O$($f $($N $)),$ where N $=$ r $$ l $+1.$ You must

use Count in your solution.

I$$ll get you started with certain parts of the algorithm, and you fill in the missing details.

Your algorithm must achieve best case running time O$(1).$

Popular$-$Sorted$($A $=[$al$,$ al$+1,...,$ ar$])$:

if l $=$ r then

$???$

end if

Let m $=$ l$+$r

$2,$ AL $=[$al$,$ al$+1,...,$ am$]$ and AR $=[$am$+1,$ am$+2,...,$ ar$]$ Give a general characterization of the the set of best case inputs for your Popular$-$Sorted algorithm, assuming N $=$ data.size$().$ State and justify its best case asymptotic running time of your Popular Sorted algorithm. Keep in mind that the requirements say that you must have O$(1)$ best case running time, but if you weren$$t able to achieve this, then state the best case running time of your algorithm and justify it$.$