Question

Solve the following recurrence relations: 1. T(n) = T(n/3) + n for n > 1 T(1)...

Solve the following recurrence relations:

1.
T(n) = T(n/3) + n for n > 1
T(1) = 1


2.
T(n) = 4T(n/2) + n^2 for n > 1
T(1) = 1

Homework Answers

Answer #1

T(n)

= T(n/3) + n

= T(n/9) + n/3 + n

=T(n/27)+ n/9 + n/3 + n

= T(n/3i) +n/3i-1 + n/3i-2 + ....... + n = n

T(n) = T(1) + n (1 + 1/3 + 1/32 + ..... + 1/3i-1 )

= T(1) + n(1(1- (1/3i)/(1- 1/3)

= 1 + 2n/3 (1- (1/3i))

Now n/3i = 1  

T(n) = 1+3n/2 (1- 1/n) = 1+3n/2 * (n-1)/n = 1+3/2*(n-1) = 3n/2- 3/2+1 = 3n/2 - 1/2 = (3n-1)/2

therefore T(n) = (3n-1)/2

(b)

T(n)

= 4T(n/2) + n2

= 4 * (4T(n/4) + (n/2)2 ) + n2

= 16T(n/4) + 2n2

= 4i T(n/2i)+in2

where

n/2i = 1

n = 2i

log 2n = i

T(n) = 4log 2 n * T(1) + (log 2n)n2 = 22log 2 n * 1 + (log 2n)n2 = n2 (1 + log2n) = n2 (log22 + log2n) = n2log2(2n)

T(n) =  n2log2(2n)

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Solve the Recurrence Relation T(n) = 2T(n/3) + 2, T(1) = 1
Solve the Recurrence Relation T(n) = 2T(n/3) + 2, T(1) = 1
Recurrence Relations Solve the following recurrence equation: f(n, k) = 0, if k > n f(n,k)...
Recurrence Relations Solve the following recurrence equation: f(n, k) = 0, if k > n f(n,k) = 1, if k = 0 f(n,k) = f(n-1, k) + f(n-1,k-1), if n >= k > 0
Problem #1. Solve the following recurrence exactly.                         9n^2 - 15n + 106        &nbs
Problem #1. Solve the following recurrence exactly.                         9n^2 - 15n + 106                    if n = 0, 1 or 2             t(n)=                         t(n-1) + 2t(n-2) - 2t(n-3)         otherwise Problem #2. Solve the following recurrence exactly.                         n                                              if n = 0, 1 2, or 3             t(n)=                         t(n-1) + t(n-3) - t(n-4)             otherwise Problem #3. Solve the following recurrence exactly.                         n + 1                                       if n = 0, or 1             t(n)=                         3t(n-1) - 2t(n-2) +...
Solve the following recurrence relation T(1) = c1 T(n) = 2*T(n/2) + c2
Solve the following recurrence relation T(1) = c1 T(n) = 2*T(n/2) + c2
Solve the following recurrence relations. If possible, use the Master Theorem. If the Master Theorem is...
Solve the following recurrence relations. If possible, use the Master Theorem. If the Master Theorem is not possible, explain why not and solve it using another approach (substitution with n = 3h or h - log3(n). a. T(n) = 7 * n2 + 11 * T(n/3) b. T(n) = 4 * n3 * log(n) + 27 * T(n/3)
Solve the recurrence relation using the substitution method: 1. T(n) = T(n/2) + 2n, T(1) =...
Solve the recurrence relation using the substitution method: 1. T(n) = T(n/2) + 2n, T(1) = 1, n is a 2’s power 2. T(n) = 2T(n/2) + n^2, T(1) = 1, n is a 2’s power
Given the following recurrence relation, convert to T(n) and solve using the telescoping method. T(2n) =...
Given the following recurrence relation, convert to T(n) and solve using the telescoping method. T(2n) = T(n) + c1 for n > 1, c2 for n = 1
Find a closed form for the following recurrence relations. Show your work. (a) an = −an−1,...
Find a closed form for the following recurrence relations. Show your work. (a) an = −an−1, a0 = 3 (b) an = an−1 − n, a0 = 5 (c) an = 2an−1 − 3, a0 = 2
Two infinite sequences {an}∞ n=0 and {bn}∞ n=0 satisfy the recurrence relations an+1 = an −bn...
Two infinite sequences {an}∞ n=0 and {bn}∞ n=0 satisfy the recurrence relations an+1 = an −bn and bn+1 = 3an + 5bn for all n ≥ 0.  Imitate the techniques used to solve differential equations to find general formulas for an and bn in terms of n.
Also write the time complexity Solve the non-linear recurrence equation using recurrence A(n) = 2A(n/2) +...
Also write the time complexity Solve the non-linear recurrence equation using recurrence A(n) = 2A(n/2) + n Solve the non-linear recurrence equation using Master’s theorem T (n) = 16T (n/4) + n
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT