next up previous
Next: Implementing Computer Algebra: basic ideas Up: A review of complexity notions Previous: Orders of magnitude

The complexity of divide-and-conquer algorithms

DIVIDE-AND-CONQUER ALGORITHMS proceed as follows.

Divide
the input problem into sub-problems.
Conquer
on the sub-problems by solving them directly if they are small enough or proceed recursively.
Combine
the solutions of the sub-problems to obtain the solution of the input problem.


EQUATION SATISFIED BY T(N). Assume that the size of the input problem increases with an integer n. Let T(n) be the time complexity of a divide-and-conquer algorithm to solve this problem. Then T(n) satisfies an equation of the form:

T(n) = a T(n/b) + f (n). (13)

where f (n) is the cost of the combine-part, a $ \geq$ 1 is the number of recursively calls and n/b with b > 1 is the size of a sub-problem.


LABELED TREE ASSOCIATED WITH THE EQUATION. Assume n is a power of b, say n = bp. To solve this equation we can associate a labeled tree $ \cal {A}$(n) to it as follows.

(1)
If n = 1, then $ \cal {A}$(n) is reduced to a single leaf by labeled T(1).
(2)
If n > 1, then the root of $ \cal {A}$(n) is labeled by f (n) and $ \cal {A}$(n) possesses a labeled sub-trees all equal to $ \cal {A}$(n/b).
The labeled tree $ \cal {A}$(n) associated with T(n) = a T(n/b) + f (n) has height p + 1. Moreover the sum of its labels is T(n).


LET US GIVE TWO EXAMPLES.


A FORMULA TO ESTIMATE T(N). Let a > 0 be an integer and let S, T  :  $ \mbox{${\mathbb N}$}$ $ \longrightarrow$ $ \mbox{${\mathbb R}$}$+ be functions such that

(i)
S(2 n$ \geq$   2 S(n) and S(n$ \geq$   n.
(ii)
If n = 2p then T(n$ \leq$   a T(n/2) + S(n).
Then for n = 2p we have
(1)
if a = 1 then

T(n) $\displaystyle \leq$ (2 - 2/nS(n) + T(1)  $\displaystyle \in$  $\displaystyle \cal {O}$(S(n)), (19)

(2)
if a = 2 then

T(n) $\displaystyle \leq$ S(n) log2(n) + T(1) n  $\displaystyle \in$  $\displaystyle \cal {O}$(log2(nS(n)), (20)

(3)
if a $ \geq$ 3 then

T(n) $\displaystyle \leq$ $\displaystyle {\frac{{2}}{{a-2}}}$$\displaystyle \left(\vphantom{ n^{{{\log}_2}(a) - 1} - 1 }\right.$nlog2(a)-1 - 1$\displaystyle \left.\vphantom{ n^{{{\log}_2}(a) - 1} - 1 }\right)$ S(n) + T(1) nlog2(a)  $\displaystyle \in$  $\displaystyle \cal {O}$(S(nnlog2(a)-1). (21)

Indeed

T(2p) $\displaystyle \leq$ a T(2p-1) + S(2p)
  $\displaystyle \leq$ a$\displaystyle \left[\vphantom{ a \, T(2^{p-2}) + S(2^{p-1}) }\right.$a T(2p-2) + S(2p-1)$\displaystyle \left.\vphantom{ a \, T(2^{p-2}) + S(2^{p-1}) }\right]$ + S(2p)
  = a2 T(2p-2) + a S(2p-1) + S(2p)
  $\displaystyle \leq$ a2$\displaystyle \left[\vphantom{ a \, T(2^{p-3}) + S(2^{p-2}) }\right.$a T(2p-3) + S(2p-2)$\displaystyle \left.\vphantom{ a \, T(2^{p-3}) + S(2^{p-2}) }\right]$ + a S(2p-1) + S(2p)
  = a3 T(2p-3) + a2 S(2p-2) + a S(2p-1) + S(2p)
  $\displaystyle \leq$ ap T(1) + $\displaystyle \Sigma_{{{j=0}}}^{{{j=p-1}}}$ aj S(2p-j)
(22)

Moreover

S(2p) $\displaystyle \geq$ S(2p-1)
S(2p) $\displaystyle \geq$ 22 S(2p-2)
$\displaystyle \vdots$ $\displaystyle \vdots$ $\displaystyle \vdots$
S(2p) $\displaystyle \geq$ 2j S(2p-j)
(23)

Thus

$\displaystyle \Sigma_{{{j=0}}}^{{{j=p-1}}}$ aj S(2p-j$\displaystyle \leq$  S(2p$\displaystyle \Sigma_{{{j=0}}}^{{{j=p-1}}}$ $\displaystyle \left(\vphantom{ \frac{a}{2} }\right.$$\displaystyle {\frac{{a}}{{2}}}$$\displaystyle \left.\vphantom{ \frac{a}{2} }\right)^{{j}}_{{}}$. (24)

Hence

T(2p$\displaystyle \leq$  ap T(1) + S(2p$\displaystyle \Sigma_{{{j=0}}}^{{{j=p-1}}}$ $\displaystyle \left(\vphantom{ \frac{a}{2} }\right.$$\displaystyle {\frac{{a}}{{2}}}$$\displaystyle \left.\vphantom{ \frac{a}{2} }\right)^{{j}}_{{}}$. (25)

For a = 1 we obtain

T(2p) $\displaystyle \leq$ T(1) + S(2p$\displaystyle \Sigma_{{{j=0}}}^{{{j=p-1}}}$ $\displaystyle \left(\vphantom{ \frac{1}{2} }\right.$$\displaystyle {\frac{{1}}{{2}}}$$\displaystyle \left.\vphantom{ \frac{1}{2} }\right)^{{j}}_{{}}$
  = T(1) + S(2p$\displaystyle {\frac{{\frac{1}{2^p} - 1}}{{\frac{1}{2} - 1}}}$
  = T(1) + S(n) (2 - 2/n).
(26)

For a = 2 we obtain

T(2p) $\displaystyle \leq$ 2p T(1) + S(2pp
  = n T(1) + S(n) log2(n).
(27)


next up previous
Next: Implementing Computer Algebra: basic ideas Up: A review of complexity notions Previous: Orders of magnitude
Marc Moreno Maza
2003-06-06