Search code examples
algorithmrecurrence

Recurrence relations with master theorem: polynomial function

let T(n) be an increasing function

T(n) = aT(n/b)+f(n)

where a >= 1 and b >= 2

To use Master theorem, one of the conditions which must be satisfied is that f(n) should be a polynomial function.

In this example, it is clearly not

T(n) = 2T(n/4) + n^(1/2) + 42 .

The book counts f(n)=n^(1/2) as a polynomial function but what I am taught is that if f(n) = n^a is a polynomial function, then a must be a natural number. Is there a special condition?

Solution

  • You might call this a generalised polynomial, but it is what is intended. Many theorems that work for 'natural number' polynomials also work for these generalised polynomials. Just think of differentiating or integrating.