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^log_ba)

Case-02:

If a = b^k and

• If p < -1, then T(n) = θ (n^log_ba)
• If p = -1, then T(n) = θ (n^log_ba.log²n)
• If p > -1, then T(n) = θ (n^log_ba.log^p+1n)

Case-03:

If a < b^k and

• If p < 0, then T(n) = O (n^k)
• If p >= 0, then T(n) = θ (n^klog^pn)

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

• 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^klog^pn).

Then, we have-

a = 25

b = 5

k = 1

p = 0

Now, a = 25  and b^k = 5¹ = 5.

Clearly, a > b^k.

So, we follow case-01.

So, we have-

T(n) = θ (n^log_ba)

T(n) = θ (n^log₅25)

T(n) = θ (n²)

Thus,

T(n) = θ (n2)