Draw the recursion tree when n = 8, where n represents the length of the array, for the following recursive method:
int sum(int array, int first, int last)
if (first == last)
int mid = (first + last) / 2;
return sum(array, first, mid) + sum(array, mid + 1, last);
· Determine a formula that counts the numbers of nodes in the recursion tree.
· What is the Big-Q for execution time?
· Determine a formula that expresses the height of the tree.
· What is the Big-Q for memory?
· Write an iterative solution for this same problem and compare its efficiency with this recursive solution.