Question

Consider the recurrence relation T(1) = 0, T(n) = 25T(n/5) +
5n.

(a) Use the Master Theorem to find the order of magnitude of
T(n)

(b) Use any of the various tools from class to find a closed-form
formula for T(n), i.e. exactly solve the recurrence.

(c) Verify your solution for n = 5 and n = 25.

Answer #1

a)

Here, a >= 1, b > 1, k >= 0 and p is a real number.

To solve recurrence relations using Master’s theorem, we compare
a with b^{k}.

Then, we follow the following cases-

**Case-01:**

If a > b^{k}, then T(n) = θ
(n^{logba})

**Case-02:**

If a = b^{k} and

- If p < -1, then T(n) = θ (n
^{logba}) - If p = -1, then T(n) = θ
(n
^{logba}.log^{2}n) - If p > -1, then T(n) = θ
(n
^{logba}.log^{p+1}n)

**Case-03:**

If a < b^{k} and

- If p < 0, then T(n) = O (n
^{k}) - If p >= 0, then T(n) = θ
(n
^{k}log^{p}n)

********************************************************************************************

- We write the given recurrence relation as T(n) = 25T(n/5) + n.
- This is because in the general form, we have θ for function f(n) which hides constants in it.
- Now, we can easily apply Master’s theorem.

We compare the given recurrence relation with T(n) = aT(n/b) + θ
(n^{k}log^{p}n).

Then, we have-

a = 25

b = 5

k = 1

p = 0

Now, a = 25 and b^{k} = 5^{1} =
5.

Clearly, a > b^{k}.

So, we follow case-01.

So, we have-

T(n) = θ (n^{logba})

T(n) = θ (n^{log525})

T(n) = θ (n^{2})

Thus,

T(n) = θ (n^{2}) |

Use Master Theorem to solve the following recurrences. Justify
your answers.
(1) T(n) = 3T(n/3) + n
(2) T(n) = 8T(n/2) + n^2
(3) T(n) = 27T(n/3) + n^5
(4) T(n) = 25T(n/5) + 5n^2

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)

Master Theorem: Let T(n) = aT(n/b) + f(n) for some constants a ≥
1, b > 1.
(1). If f(n) = O(n logb a− ) for some constant > 0, then T(n)
= Θ(n logb a ).
(2). If f(n) = Θ(n logb a ), then T(n) = Θ(n logb a log n).
(3). If f(n) = Ω(n logb a+ ) for some constant > 0, and
af(n/b) ≤ cf(n) for some constant c < 1, for all large n,...

Consider below recurrence relation
f_(n )=f_(n-1)+ f_(n-2) for n ≥ 3. f_(1 )=1 and f_2 = 3
(a) Please compute the first seven numbers in this sequence.
(b) Find the closed form for this recurrence relation. Solving
the characteristic equation, and solving for constants

Solve the Recurrence Relation T(n) = 2T(n/3) + 2, T(1) = 1

Consider the nonhomogeneous linear recurrence relationan= 3an−1+
3n. (a) Show thatan=n3nis a solution of this recurrence relation.
(b) Use Theorem 5 to find all solutions to this recurrence
relation. (c) Find the solution witha0= 2.

Solve the following recurrence relation
T(1) = c1
T(n) = 2*T(n/2) + c2

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

Write a Recursive Function Algorithm to find the terms of
following recurrence relation.
t(1)=3
t(k)=2×t(k-1)-5 (n>1).
and (ii) If you call z←t(4) in a program then what value the
program will use for z?

Consider the following recursive algorithm. Algorithm Test
(T[0..n − 1]) //Input: An array T[0..n − 1] of real numbers if n =
1 return T[0] else temp ← Test (T[0..n − 2]) if temp ≥ T[n − 1]
return temp else return T[n − 1] a. What does this algorithm
compute? b. Set up a recurrence relation for the algorithm’s basic
operation count and solve it.

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 20 minutes ago

asked 30 minutes ago

asked 36 minutes ago

asked 38 minutes ago

asked 48 minutes ago

asked 49 minutes ago

asked 57 minutes ago

asked 57 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago