Formula: complexity estimates for divide-and-conquer algorithms

Let $T(n)$ be the running time estimate of a divide-and-conquer algorithm. Assume that $T(n)$ satisfies a relation of the form:

$$T(n) \leq a \, T(n/b) + S(n)$$ (5)

where $S(n)$ is the cost of the combine-part, $a \geq 3$ is the number of recursive calls and $n/b$ is the size of a sub-problem, with $b$ an integer greater than $1$ . Assume that the following holds for all $n$ :

$$S(b \, n) \ \geq \ b S(n) \ \ {\rm and} \ \ S(n) \ \geq \ n.$$

Then we have $T(n) \ \in \ {\cal O}(S(n) \, n^{{{\log}_b}(a) - 1})$ .