Recursion for runtime of divide and conquer algorithms
The total work is given by the sum of a geometric progression. In particular, let $r = a/b^d$, then total work = $O(n^d)\times (1+r+r^2+\ldots+r^p)$, where $p$ is the maximum depth.

Let $S = (1+r+r^2+\ldots+r^p)$.

If $r&gt;1$, then $S = \frac{r^p-1}{r-1}+r^p = O(r^p)$.

If $r&lt;1$, then $S \leq 1+r+r^2+\ldots = \frac{1}{1-r} = O(1)$.