Question

Give upper and lower bounds for T(n) in the following recurrence: T(n) = 3T(n/4) + n

Answer 1

Solution:

Given,

=>T(n) = 3T(n/4) + n

Explanation:

=>T(n) = 3T(n/4) + n

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

Master's theorem,

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

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

Compare (1) and (2)

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

Finding b^k:

=>b^k = 4^1

=>b^k = 4

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

=>T(n) = (n^k*(logn)^p)

=>T(n) = (n^1*(logn)^0)

=>T(n) = (n)

=>Using definition of big-theta, upper bound = O(n) and lower bound = (n)

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