Consider following recursive function:



a. Draw the recursion tree that results from the call F(A=[3, 5, 2, 4, 8, 9, 3, 4], 0, 7), and explain what this function computes as its output in general.

b. Write the recurrence that expresses the running time of this function.

c. Express the running time in big-O notation by solving the recurrence using repea
 

• 
  
  • 
    

Transcribed Image Text:

int F(vector &nums, int left, int right){ right) return 0; if (left if (left == right) return nums[left]; int middle left + (right-left)/2; = return F(nums, left, middle) + F(nums, middle+1, right); }| int F(vector &nums, int left, int right){ right) return 0; if (left if (left == right) return nums[left]; int middle left + (right-left)/2; = return F(nums, left, middle) + F(nums, middle+1, right); }|