Question

Solve the following recurrences using master method
T(n) = 9T(n/3) + n^3
T(n) = 8T(n/2) +n^3

Answer 1

Explanation:

We compare the given recurrence relation with T(n) = aT(n/b) + θ (nklogpn).

Then, we have-

a = 3

b = 2

k = 2

p = 0

Now, a = 3 and bk = 22 = 4.

Clearly, a < bk.

So, we follow case-03.

Since p = 0, so we have-

T(n) = θ (nklogpn)

T(n) = θ (n2log0n)

Thus,

T(n) = θ (n2)

Answer 2

Answer:

Given T(n)=9T(n/3)+n3,

I know that a=9, b=3, and f(n)=n3

and nlog39=n2

thus Case 3 applies: nlogba<f(n), n2<n3.

Can someone explain how to apply the regularity condition and how to check the regularity condition?

af(n/b)≤cf(n) where c<1