$9.[35$ points$]$ Consider the following C$++$ code that sums all of the elements of array a$,$ where n$,$

the number of elements in a$,$ is always a positive integer power of $2.$

int sumArray $($int a$[],$ int low, int high$)$

$\}$

if $($low$==$high$)$

return a $[$low$]$;

int mid $=($low high$)/2$;

int lsum $=$ sumArray $($a$,$ low, mid$)$;

int rsum $=$ sumArray $($a$,$ mid $+1,$ high$)$;

return lsum $+$ rsum;

a$.[8$ points$]$ Set up a recurrence relation for the time complexity T$($n$)$ and briefly explain how

you arrived at the recursion $($i$.$e$.,$ what the terms of your recurrence relation represent$).$

Assume that each operation $($addition$,$ division, and comparison$)$ takes constant time $1$ to

compute. Assignments, function calls, and return statements are free, though operations

used in them are not. Include an appropriate non$-$recursive value for the smallest n$.$

b$.[10$ points$]$ Find a closed$-$form solution for the recurrence you defined in $($a$)$ using either

the telescoping or substitution method.