We compare two different divide and conquer algorithms for the same problem.

Algorithm A: On an array of size n$,$ the algorithm produces FOUR sub arrays, each of size n$2$ performing $\backslash$Theta $($n$2)$ work in the process. The time taken to combine the output of the sub problems is $\backslash$Theta $($n$).$

Algorithm B: On an array of size n$,$ the algorithm produces THREE sub arrays, each of size n$2$ performing $\backslash$Theta $($n$2)$ work in the process. The time taken to combine the output of the sub problems is $\backslash$Theta $($n$)$

$.$

$1)$ Write down the recurrences for the running time A$($n$)$ for algorithm A and B$($n$)$ for algorithm B on inputs of size n$.$ You do not need to write out the base case.

$2)$ Solve for A$($n$)$ using the master method to derive a Theta bound on worst case running time of algorithm A$.$

$3)$ Solve for B$($n$)$ using the master method to derive a Theta bound on worst case running time of algorithm B$.$

$---$

Master Method

The recurrence T$($n$)=$aT$($nb$)+\backslash$Theta $($nc$)$

with base case

T$(1)=\backslash$Theta $(1)$

has the solution

Case $1$ logba$>$c

then T$($n$)=\backslash$Theta $($nlogb$($a$))$

Case $2$ logba$=$c

then T$($n$)=\backslash$Theta $($nlogb$($a$)$log$($n$))$

Case $3$ logba