Partitioning Arrays

The Partition algorithm for an array uses one of its elements, called a pivot, and returns a permutation of the array where the elements to the left of its position in the response are all smaller than it$,$ and the elements to the right are all greater than or equal to it$.$ Additionally, the function returns the new position of the pivot element.

For example, given the array below:

A $=[5,2,4,1,3,7,0,9,7]$

And using the last element as the pivot, a possible solution could be:

A $=[4,2,5,1,0,3,7,7,9]$

With the pivot index equal to $6.$

Note that the algorithm's definition does not specify that the relative order of the original elements should be preserved $($e$.$g$.,$ Element $5$ was before $4$ and $2).$

If the following C code is provided, implementing a version of the algorithm:size$\_$t partition$($int a$[],$ int n$)\{$

$//$ Get pivot element

int pivot $=$ a$[$n $-1]$;

$//$ Create two temp arrays to hold smaller and larger elements than pivot

int$*$ smaller $=$ malloc$($sizeof$($int$)*$ n$)$;

int$*$ larger $=$ malloc$($sizeof$($int$)*$ n$)$;

$//$ Init arrays insertion indexes

size$\_$t smaller$\_$idx $=0$;

size$\_$t larger$\_$idx $=0$;

size$\_$t idx;

$//$ Iterate over all elements and copy to corresponding array

for $($size$\_$t idx $=0$; idx $<$ n $-1$; idx$++)\{$

$//$ Check element smaller than pivot

if $($a$[$idx$]<$ pivot$)$

$//$ Copy to smaller array

smaller$[$smaller$\_$idx$++]=$ a$[$idx$]$;

else

$//$ Copy to larger array

larger$[$larger$\_$idx$++]=$ a$[$idx$]$;

$\}$

$//$ Set pivot index

size$\_$t pivot$\_$idx $=$ smaller$\_$idx;

$//$ Insert smaller elements to original array

for $($idx $=0$; idx $<$ pivot$\_$idx; idx$++)$

a$[$idx$]=$ smaller$[$idx$]$;

$//$ Copy pivot to correct position

a$[$pivot$\_$idx$]=$ pivot;

$//$ Insert larger elements to original array

for $($idx $=0$; idx $<$ pivot$\_$idx; idx$++)$

a$[$pivot$\_$idx $+$ idx $+1]=$ larger$[$idx$]$;

$//$ Free temp arrays

free$($smaller$)$;

free$($larger$)$;

$//$ Return pivot index

return pivot$\_$idx;

$\}$Requested:

$($a$)$ Find the asymptotic runtime for the algorithm. Assume malloc and free run in O$(1).$

$($b$)$ The time for malloc and free is implementation$-$dependent. Assuming now the times for these operations are O$($n$),$ does this affect the asymptotic runtime of the algorithm?