Chapter 8.3, Problem 37E

In Exercises 29-33, assume that f is an increasing function satisfying the recurrence relation $f\left(n\right)=af\left(n/b\right)+c{n}^d$, where $a\ge 1$ , b is an integer greater than 1, and c and dare positive real numbers. These exercises supply a proof of Theorem 2.

Give a big-O estimate for the function f in Exercise 36 if f is an increasing function.