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 (ie , proof by induction). Thus, you must show that T(n) > cn2 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. b. Show that T(n) is O(n3) using the substitution method (i.e., proof by induction). Thus, you must show that T(n) cn3 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