# Recursion for runtime of divide and conquer algorithms

A divide and conquer algorithm's work at a specific level can be simplified into the equation:

$\qquad \displaystyle O\left(n^d\right) \cdot \left(\frac{a}{b^d}\right)^k$

where $n$ is the size of the problem, $a$ is the number of sub problems, $b$ is the factor the size of the problem is broken down by at each recursion, $k$ is the level, and $d$ is the exponent for Big O notation (linear, exponential etc.).

The book claims if the ratio is greater than one the sum of work is given by the last term on the last level, but if it is less than one the sum of work is given by the first term of the first level. Could someone explain why this is true?

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>1$, then $S = \frac{r^p-1}{r-1}+r^p = O(r^p)$.
If $r<1$, then $S \leq 1+r+r^2+\ldots = \frac{1}{1-r} = O(1)$.
• Could you please expand on how the equations simplify to $O(r^p)$ and $O(1)$? I don't see the relation. Why are you disregarding $\frac{r^p -1}{r-1}$ and the denominator $1-r$? – user1422 May 9 '12 at 12:36
• Thanks.I understand $O(r^p)$, but how is the second one a constant? Isn't it a rational function? It approaches infinity as $r$ gets larger. – user1422 May 9 '12 at 14:45
• Here the variable is $n$. $r$ is a constant since it depends only on $a$ and $b$, which are constants themselves. – Vinayak Pathak May 9 '12 at 17:42