Question 8 4 pts Mark all that apply by writing either T (for true) or F (for false) in the blank box before each statement. Consider the recurrence n 9 Applying the Master Theorem we conclude that: The Master Theorem does not apply to this recurrence. Function f (n) = in satisfies the regularity condition. T(n) 9 72 Inn the 3rd case. Any 0 2 Using repeated substitution, we can guess that the tight bound for this recurrence is T(n) (c") for a constant c = (hint: c is one of 2, 3, 4, 5, 6, 7, 8, or 9). Then using induction to prove its lower bound, we can show that a.c" 1 and a constant a as large as a = .but not larger (hint: a is one of 1, 2/3, 1/2, 2/5, 1/3. 2/7, 1/4, or 2/9). Finally, using induction to prove its upper bound, we can show that T(n) 1 and a constant bas small as b but not smaller (hint: b is one of 1, 2, 3, 4, 5, 6, 7, or 8)