Consider the recurrence relation T(n) = 8T(n/2) + n^2 with initial condition T(1
ID: 3123763 • Letter: C
Question
Consider the recurrence relation T(n) = 8T(n/2) + n^2 with initial condition T(1) = 1. where n is restricted to being a power of 2. (This recurrence relation arose in analyzing matrix multiplication in Section 7.2.) (a) By plugging it into the recurrence relation and initial condition, show that T(n) = 2n^3 - n^2 is the solution. (b) Compute T(16) both from the recurrence and from the explicit solution, and note that the same answer is obtained in each case. Determine which of the following recurrence relations are homogeneous recurrence relations with constant coefficient. Determine the order of that are, and explain why the others are not. (a) a_n = a_n - 3. (b) a_n = Squareroota_n - 1. (c) a_n = 5. (d) a_n = 3n^2 a_n - 1 - 3n^2a_n - 2. Use the iterative approach to solve the following recurrence relations and initial conditions. (a) T(n) = 2T(n - 1), T(0) = 1. (b) T(n) = 2T(n - 1), T(0) = 0. (c) T(n) = 2T(n - 1) + 1, T(0) = 0. (d) A_n = 2f(n/2) + Squareroot n. Use Theorem 1 to estimate f(n) in big-oh terms if f satisfies the given recurrence relation. Assume that f satisfies the hypotheses of the theorem, (a) f(n) = 3f(n/3) + 7n. b) f(n) = 4f(n/2) + n^2. (c) f(n) = f(n/2) + n. (d) f(n) = 2f(n/2) + Squareroot n.Explanation / Answer
4. (a) T(n) = 2T(n-1)
Using the relation recursively
=> T(n) = 2 * 2T(n-2) = 22 T(n-2)
=> T(n) = 22 * 2T(n-3) = 23 T(n-3)
and so on
=> T(n) = 2nT(0)
Given T(0) = 1
So T(n) = 2n*1 = 2n
(b) T(0) = 0
=> T(n) = 2n*0 = 0.
(c) T(n) = 2T(n-1) + 1
Using the relation recursively
=> T(n) = 2 * [2T(n-2) + 1] + 1 = 22 T(n-2) + 2 + 1
=> T(n) = 22 [ 2T(n-3) + 1] + 2 = 23 T(n-3) + 22 + 2 + 1
and so on
=> T(n) = 2nT(0) + 2n-1 + 2n-2 + .....22 + 2 + 1
Given T(0) = 0
So T(n) = 2n*0 + 2n-1 + 2n-2 + .....22 + 2 + 1
=> T(n) = 2n-1 + 2n-2 + .....22 + 2 + 1
The terms consititute a GP with ratio r = 2 and initial value a = 1
So T(n) = 1(2n-1)/(2-1)
=> T(n) = 2n -1
(d) An = 3 + 2An-1
Using definition recursively,
An = 3 + 2 [3 + 2An-2]
An = 3 + 2*3 + 22An-2
An = 3 + 2*3 + 22 [3 + 2An-3]
An = 3 + 2*3 + 22*3 + 23An-3
and so on
=> An = 3 + 2*3 + 22*3 ....... + 2n-1*3 + 2nA0
=> An = 3 (1+2+22+.......2n-1) + 2nA0
Given A0 = 0
=> An = 3 (1+2+22+.......2n-1) + 0
The terms in the bracket are in GP with ratio 2 and initial value 1
=> An = 3 * (2n -1) / (2-1)
=> An = 3 * (2n -1)