**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
MATHEND000#.
Assume that the size of the input problem increases with an integer
.
Let
be the time complexity of a divide-and-conquer algorithm
to solve this problem.
Then
satisfies an equation of the form:
**

(14) |

*
*

*
*

**LABELED TREE ASSOCIATED WITH THE EQUATION.
Assume
is a power of
, say
To solve this equation we can associate a labeled tree
to it
as follows.
**

- If , then is reduced to a single leaf by labeled .
- If , then the root of is labeled by and possesses labeled sub-trees all equal to .

*
*

*
*

**LET US GIVE TWO EXAMPLES.
**

- Consider the relation:
(15)

We obtain:(16)

Hence we have:(17)

- Consider the relation:
(18)

We obtain:(19)

*
*

*
*

**A FORMULA TO ESTIMATE
MATHEND000#.
Let
be an integer and let
be functions
such that
**

- and .
- If then

- if
then
(20)

- if
then
(21)

- if
then
(22)

(23) |

(24) |

(25) |

(26) |

(27) |

(28) |

*
*

2008-01-07