Computer Science Homework Help

I have a homework assignment that I already have answers for but they need to be verified and it also needs to include inductive proof and correct post conditions; Please see attached pdf for full assignment.

1. Given the following two functions:
   •  f(n) = 3n2 + 5
   •  g(n) = 53n + 9
     Use L’Hopital’s rule and limits to prove or disprove each of the following:
      f(g)
      g(f)
2. Rank the following functions from lowest asymptotic order to highest. List any two or
   more that are of the same order on the same line.
    2
    3+5
    log2
    3+2 2+1
    3n
    log3
    2+5 +10
    log2
    10 +7
    √
3. 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- for execution time?
   •  Determine a formula that expresses the height of the tree.
   •  What is the Big- for memory?
   •  Write an iterative solution for this same problem and compare its efficiency with this
     recursive solution.

4. Using the recursive method in problem 3 and assuming n is the length of the array.

•  Modify the recursion tree from the previous problem to show the amount of work on
  each activation and the row sums.
•  Determine the initial conditions and recurrence equation.
•  Determine the critical exponent.
•  Apply the Little Master Theorem to solve that equation.
•  Explain whether this algorithm optimal.