Question

Problem 4 (2+2+2+2 marks). Analyze the following recurrence relations using the Master Theorem, and give a Θbound for each. (a) T(N) = 2T(N/4) + 1. (b) T(N) = 2T(N/4) + √ N. (c) T(N) = 2T(N/4) + N2 . (d) T(N) = 9T(N/3) + N.

Answer 1

Solution:

(4)

(a)

Given,

=>T(N) = 2T(N/4) + 1

Explanation:

=>T(N) = 2T(N/4) + 1

=>T(N) = 2T(N/4) + (1)...(1)

Master's theorem:

=>T(n) = aT(n/b) + (n^k(logn)^p)....(2)

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

Compare (1) and (2)

=>a = 2, b = 4, k = 0 and p = 0

Finding b^k:

=>b^k = 4^0

=>b^k = 1

=>a > b^k hence first case of Master's theorem.

=>T(N) = (N^log_b(a))

=>T(N) = (N^log₄(2))

=>T(N) = ()

(b)

Given,

=>T(N) = 2T(N/4) +

Explanation:

=>T(N) = 2T(N/4) +

=>T(N) = 2T(N/4) + ()....(1)

Master's theorem:

=>T(n) = aT(n/b) + (n^k(logn)^p)....(2)

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

Compare (1) and (2)

=>a = 2, b = 4, k = 1/2 and p = 0

Finding b^k:

=>b^k = 4^1/2

=>b^k = 2

=>a = b^k hence second case of Master's theorem.

=>T(N) = (N^log_b(a)*(logN)^p+1)

=>T(N) = (N^log₄(2)*(logN)^0+1)

=>T(N) = (logN)

(c)

Given,

=>T(N) = 2T(N/4) + N^2

Explanation:

=>T(N) = 2T(N/4) + N^2

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

Master's theorem:

=>T(n) = aT(n/b) + (n^k(logn)^p)....(2)

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

Compare (1) and (2)

=>a = 2, b = 4, k = 2 and p = 0

Finding b^k:

=>b^k = 4^2

=>b^k = 16

=>a < b^k hence third case of Master's theorem.

=>T(N) = (N^k(logN)^p)

=>T(N) = (N^2(logN)^0)

=>T(N) = (N^2)

(d)

Given,

=>T(N) = 9T(N/3) + N

Explanation:

=>T(N) = 9T(N/3) + N

=>T(N) = 9T(N/3) + (N)....(1)

Master's theorem:

=>T(n) = aT(n/b) + (n^k(logn)^p)....(2)

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

Compare (1) and (2)

=>a = 9, b = 3, k = 1 and p = 0

Finding b^k:

=>b^k = 3^1

=>b^k = 3

=>a > b^k hence first case of Master's theorem.

=>T(N) = (N^log_b(a))

=>T(N) = (N^log₃(9))

=>T(N) = (N^2)

I have explained each and every part with the help of statements attached to the answer above.