Algorithms

1 Recurrence relation using substitution method. Consider the following recurrence relation: T(n) 6T(n/2) +T(n/4) +8n a. Show that T(n) is (n2) using the substitution method (i.e., proof by induction). Thus, you must show that T(n) for sme constant c0 for large enough . You st not use asymptotic notation in your proof by induction. Furthermore, your proof must conclude with the same constant c as in the induction hypothesis. b. Show that T(n) is O(n3) using the substitution method (i.e, proof by induction). Thus, you must show that T(n) en for some constant c>0 for large enough n. You must not use asymptotic notation in your proof by induction. Furthermore, your proof must conclude with the same constant c as in the induction hypothesis. 2 Recurrence relation using recursion tree/iteration method. Use the recursion tree/iteration method to find an asymptotic upper bound for the following re- currence relaton. Show all of your work. T(n) = 2T(n/4) + 8n. 3 Recurrence relation using recursion tree/iteration method. Use the recursion tree/iteration method to find an asymptotic upper bound for the following re- currence relation. Show al of your work T(n) - 6T(n/2) +n2