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?


1 Answer 1


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)$.

  • $\begingroup$ 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$? $\endgroup$
    – user1422
    May 9, 2012 at 12:36
  • $\begingroup$ That's just how the big O notation works. 1/1-r is a constant and any constant can be written as O(1). For the other expression, big O picks out the highest power. I recommend reading up on big O on wikipedia if you are having troubles understanding this. $\endgroup$ May 9, 2012 at 13:49
  • $\begingroup$ 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. $\endgroup$
    – user1422
    May 9, 2012 at 14:45
  • 2
    $\begingroup$ Here the variable is $n$. $r$ is a constant since it depends only on $a$ and $b$, which are constants themselves. $\endgroup$ May 9, 2012 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.