## 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 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)

where is the cost of the combine-part, is the number of recursively calls and with is the size of a sub-problem.

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 .
The labeled tree associated with has height . Moreover the sum of its labels is .

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
Then for we have
if then

 (20)

if then

 (21)

if then

 (22)

Indeed

 (23)

Moreover

 (24)

Thus

 (25)

Hence

 (26)

For we obtain

 (27)

For we obtain

 (28)

Marc Moreno Maza
2008-01-07