Question

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

Answer #1

T(n)

= T(n/3) + n

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

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

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

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

= T(1) + n(1(1- (1/3^{i})/(1- 1/3)

= 1 + 2n/3 (1- (1/3^{i}))

Now n/3^{i} = 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) + n^{2}

= 4 * (4T(n/4) + (n/2)^{2} ) + n^{2}

= 16T(n/4) + 2n^{2}

= 4^{i} T(n/2^{i})+in^{2}

where

n/2^{i} = 1

n = 2^{i}

log _{2}n = i

T(n) = 4^{log 2 n} * T(1) + (log
_{2}n)n^{2} = 2^{2log 2 n} * 1 +
(log _{2}n)n^{2} = n^{2} (1 +
log_{2}n) = n^{2} (log_{2}2 +
log_{2}n) = n^{2}log_{2}(2n)

**T(n)
= n ^{2}log_{2}(2n)**

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) = 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
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 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) = 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) = 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, a0 = 3 (b) an = an−1 − n, a0 = 5 (c) an
= 2an−1 − 3, a0 = 2

Two inﬁnite 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 diﬀerential equations to ﬁnd 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) + n
Solve the non-linear recurrence equation using Master’s
theorem
T (n) = 16T (n/4) + n

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 14 minutes ago

asked 39 minutes ago

asked 51 minutes ago

asked 52 minutes ago

asked 54 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago