Question

solve the recurrence T(n)=9T(n/3)+n with
master method

Answer 1

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