The following algorithm finds the sum of all elements in an array using a divide and conquer strategy.

func sumArray(A, low, high)

if low > high

return 0

if low = high

return A[low]

mid <- (high + low) / 2

leftSum <- sumArray(A, low, mid)

rightSum <- sumArray(A, mid+1, high)

return leftSum + rightSum

(a) Give a recurrence relation for the worst case performance of this algorithm.

(b) Find the asymptotic complexity of your recurrence relation