Question

Use the substitution method to show that each of the following recurrences defined on the reals has the asymptotic solution specified: a.T(n)=T(n−1)+nhas solutionT(n)=O(n 2 ). b.T(n)=T(n/2)+Θ(1)has solutionT(n)=O(lgn). c.T(n)=2T(n/2)+nhas solutionT(n)=Θ(nlgn). d.T(n)=2T(n/2+17)+nhas solutionT(n)=O(nlgn). e.T(n)=2T(n/3)+Θ(n)has solutionT(n)=Θ(n)f.T(n)=4T(n/2)+Θ(n)has solutionT(n)=Θ(n 2)

Answer 1

To use the substitution method, we replace T(n) with its asymptotic solution in the recurrence relation and show that the solution satisfies the equation. The recurrences given have the following asymptotic solutions: a. T(n) = O(n^2), b. T(n) = O(log n).

Step-by-step explanation:

To use the substitution method, we replace T(n) with its asymptotic solution in the recurrence relation and show that the solution satisfies the equation. Let's go through each of the recurrences:

a. T(n) = T(n-1) + n

Assume T(n) = O(n^2), so T(n-1) = O((n-1)^2).
Substituting these values in the recurrence relation:
O(n^2) = O((n-1)^2) + n
We can see that the equation holds true. Therefore, T(n) = O(n^2).

b. T(n) = T(n/2) + Θ(1)

Assume T(n) = O(log n), so T(n/2) = O(log(n/2)).
Substituting these values in the recurrence relation:
O(log n) = O(log(n/2)) + Θ(1)

We can see that the equation holds true. Therefore, T(n) = O(log n).