Draw the recursion tree when n = 8, where n represents

  

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)

          return array[first];

    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.