[SOLVED] CSC6013 Module 5- Back Substitution

Compute the complexity of the recursive algorithms based on the recursive equation and stop condition. Show your work, not just your final answer.
1. T(n) = 2T(n-1) + 1 and T(0) = 1
a. You can compute this complexity as a tight upper bound.
2. T(n) = T(n-2) + n2 and T(0) = 1
a. Hint: Assume n is even; that is, n = 2k for some integer k.
3.T(n) = T(n-1) + 1/n and T(1) = 1
a. Hint: Go online and find a formula for the sum of the first n terms of the
“harmonic series”.
Master Method
Compute the complexity of the recursive algorithms based on the recursive equation and stop condition. Show your work, not just your final answer.
4. T(n) = 2T(n/4) + 1 and T(0) = 1
a. Be sure to rewrite 1 as n0.
5. T(n) = 2T(n/4) + n1/2 and T(0) = 1
a. Note that n1/2 is the square root of n.
6.T(n) = 2T(n/4) + n2 and T(0) = 1
a. This is similar to the previous one.
Master Method
Compute the complexity of the recursive algorithms based on the recursive equation and stop condition. Show your work, not just your final answer.
7.T(n) = 10T(n/3) + n2 and T(0) = 1
a. In your answer, round the value of the logarithm to 2 decimal places.
b. Remember that the logb(a) is equal to log2 (a) / log2 (b).
8.T(n) = 2T(2n/3) + 1 and T(0) = 1
a. In your answer, round the value of the logarithm to 2 decimal places.
b. Be sure to rewrite 1 as n0.
c. Remember that the logb(a) is equal to log2 (a) / log2 (b).
d. Hint: rewrite 2n / 3 as n / (3/2)