3. Consider the following recursive function: int F(vector &nums, int left, int right){ }| if (left...

  

Transcribed Image Text:

3. Consider the following recursive function: int F(vector &nums, int left, int right){ }| if (left if (left right) return 0; right) return nums[left]; int middle left + (right-left)/2; return F(nums, left, middle) + F(nums, middle+1, right); 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 repeated expansions. 3. Consider the following recursive function: int F(vector &nums, int left, int right){ }| if (left if (left right) return 0; right) return nums[left]; int middle left + (right-left)/2; return F(nums, left, middle) + F(nums, middle+1, right); 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 repeated expansions.