1
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • $\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 '12 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$ – Vinayak Pathak May 9 '12 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 '12 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$ – Vinayak Pathak May 9 '12 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy