notation, but do not use it
4. What’s wrong with this proof? (9 points) Consider the following recurrence relation:
T(n) =T( – 5) + 10 – 1
for n > 5, where T(0) = T(1) = T(2) = T(3) = T(4) = 1. Consider the following three
arguments.
1. Claim: T(n) O(n). To see this, we will use strong induction. The inductive
hypothesis is that T(k) O(k) for all 5 <k <n. For the base case, we see
T(5) = T(0) +10.5 = 51 = 0(1). For the inductive step, assume that the inductive
hypothesis holds for all k < n. Then
T(n) = T(n – 5) + 10n,
and by induction T(n-5) = O(n – 5), so
T(n) = O(n – 5) + 10n = O(n).
This establishes the inductive hypothesis for n. Finally, we conclude that T(n)
O(n) for all n
Select the correct answer from above options
