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:
![$\displaystyle T(n) = a \, T(n/b) + f(n).$](img115.png) |
(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:
![$\displaystyle T(n) = 2 \, T(n/2) + n^2.$](img127.png) |
(15) |
We obtain:
![$\displaystyle T(n) = n^2 + \frac{n^2}{2} + \frac{n^2}{4} + \frac{n^2}{8} + \cdots + \frac{n^2}{2^p} + n\, T(1).$](img128.png) |
(16) |
Hence we have:
![$\displaystyle T(n) \in {\Theta}(n^2).$](img129.png) |
(17) |
- Consider the relation:
![$\displaystyle T(n) = 3 T(n/3) + n.$](img130.png) |
(18) |
We obtain:
![$\displaystyle T(n) \in {\Theta}({\log}_3(n) n).$](img131.png) |
(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
![$\displaystyle T(n) \leq (2 - 2/n) \, S(n) + T(1) \ \in \ {\cal O}(S(n)),$](img141.png) |
(20) |
- if
then
![$\displaystyle T(n) \leq S(n) \, {{\log}_2}(n) + T(1) \, n \ \in \ {\cal O}({{\log}_2}(n) \, S(n)),$](img143.png) |
(21) |
- if
then
![$\displaystyle T(n) \leq \frac{2}{a-2} \left( n^{{{\log}_2}(a) - 1} - 1 \right) ...
...n) + T(1) \, n^{{{\log}_2}(a)} \ \in \ {\cal O}(S(n) \, n^{{{\log}_2}(a) - 1}).$](img145.png) |
(22) |
Indeed
![\begin{displaymath}\begin{array}{rcl} T(2^p) & \leq & a \, T(2^{p-1}) + S(2^p) \...
..., T(1) + {\Sigma}_{j=0}^{j=p-1} \ a^j \, S(2^{p-j}) \end{array}\end{displaymath}](img146.png) |
(23) |
Moreover
![\begin{displaymath}\begin{array}{rcl} S(2^p) & \geq & 2 \, S(2^{p-1}) \\ S(2^p) ...
...vdots & \vdots \\ S(2^p) & \geq & 2^j \, S(2^{p-j}) \end{array}\end{displaymath}](img147.png) |
(24) |
Thus
![$\displaystyle {\Sigma}_{j=0}^{j=p-1} \ a^j \, S(2^{p-j}) \ \leq \ S(2^p) \, {\Sigma}_{j=0}^{j=p-1} \ {\left( \frac{a}{2} \right)}^j.$](img148.png) |
(25) |
Hence
![$\displaystyle T(2^p) \ \leq \ a^p \, T(1) + S(2^p) \, {\Sigma}_{j=0}^{j=p-1} \ {\left( \frac{a}{2} \right)}^j.$](img149.png) |
(26) |
For
we obtain
![\begin{displaymath}\begin{array}{rcl} T(2^p) & \leq & T(1) + S(2^p) \, {\Sigma}_...
...\frac{1}{2} - 1} \\ & = & T(1) + S(n) \, (2 - 2/n). \end{array}\end{displaymath}](img150.png) |
(27) |
For
we obtain
![\begin{displaymath}\begin{array}{rcl} T(2^p) & \leq & 2^p \, T(1) + S(2^p) \, p \\ & = & n \, T(1) + S(n) \, {\log}_2(n). \end{array}\end{displaymath}](img151.png) |
(28) |
Marc Moreno Maza
2008-01-07