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 + 9Use 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 ormore 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 thefollowing 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 thisrecursive 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 oneach 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.