Consider the following recurrence relation: T(n) = 6T(n/2) + T(n/4)+8n a. Show that T(n) is (n)...

 

Transcribed Image Text:

Consider the following recurrence relation: T(n) = 6T(n/2) + T(n/4)+8n a. Show that T(n) is (n) using the substitution method (i.e., proof by induction). Thus, you must show that T(n) > cn 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(n) using the substitution method (i.e., proof by induction). Thus, you must show that T(n) cn 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. Consider the following recurrence relation: T(n) = 6T(n/2) + T(n/4)+8n a. Show that T(n) is (n) using the substitution method (i.e., proof by induction). Thus, you must show that T(n) > cn 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(n) using the substitution method (i.e., proof by induction). Thus, you must show that T(n) cn 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.