The complexity of divide-and-conquer algorithms

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

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

(14)

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

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

(1) mathend000#: If n = 1 mathend000#, then $\cal {A}$ (n) mathend000# is reduced to a single leaf by labeled T(1) mathend000#.
(2) mathend000#: If n > 1 mathend000#, then the root of $\cal {A}$ (n) mathend000# is labeled by f (n) mathend000# and $\cal {A}$ (n) mathend000# possesses a mathend000# labeled sub-trees all equal to $\cal {A}$ (n/b) mathend000#.

The labeled tree $\cal {A}$ (n) mathend000# associated with T(n) = a T(n/b) + f (n) mathend000# has height p + 1 mathend000#. Moreover the sum of its labels is T(n) mathend000#.

LET US GIVE TWO EXAMPLES.

Consider the relation:

T(n) = 2 T(n/2) + n². (15)

We obtain:

T(n) = n² + $\displaystyle {\frac{{n^2}}{{2}}}$ + $\displaystyle {\frac{{n^2}}{{4}}}$ + $\displaystyle {\frac{{n^2}}{{8}}}$ + ^... + $\displaystyle {\frac{{n^2}}{{2^p}}}$ + n T(1). (16)

Hence we have:

T(n) $\displaystyle \in$ $\displaystyle \Theta$ (n²). (17)
Consider the relation:

T(n) = 3T(n/3) + n. (18)

We obtain:

T(n) $\displaystyle \in$ $\displaystyle \Theta$ (log₃(n)n). (19)

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

(i) mathend000#: S(2 n) $\geq$ 2 S(n) mathend000# and S(n) $\geq$ n mathend000#.
(ii) mathend000#: If n = 2^p mathend000# then T(n) $\leq$ a T(n/2) + S(n). mathend000#

Then for n = 2^p mathend000# we have

(1) mathend000#

if a = 1 mathend000# then

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

(20)

(2) mathend000#

if a = 2 mathend000# then

T(n) $\displaystyle \leq$ S(n) log₂(n) + T(1) n $\displaystyle \in$ $\displaystyle \cal {O}$ (log₂(n) S(n)),

(21)

(3) mathend000#

if a $\geq$ 3 mathend000# then

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

(22)

Indeed

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

(23)

Moreover

S(2^p)	$\displaystyle \geq$	2 S(2^p-1)
S(2^p)	$\displaystyle \geq$	2² S(2^p-2)
$\displaystyle \vdots$	$\displaystyle \vdots$	$\displaystyle \vdots$
S(2^p)	$\displaystyle \geq$	2^j S(2^p-j)

(24)

Thus

$\displaystyle \Sigma_{{{j=0}}}^{{{j=p-1}}}$ a^j S(2^p-j) $\displaystyle \leq$ S(2^p) $\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)

Hence

T(2^p) $\displaystyle \leq$ a^p T(1) + S(2^p) $\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}}_{{}}$ .

(26)

For a = 1 mathend000# we obtain

T(2^p)	$\displaystyle \leq$	T(1) + S(2^p) $\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(2^p) $\displaystyle {\frac{{\frac{1}{2^p} - 1}}{{\frac{1}{2} - 1}}}$
	=	T(1) + S(n) (2 - 2/n).

(27)

For a = 2 mathend000# we obtain

T(2^p)	$\displaystyle \leq$	2^p T(1) + S(2^p) p
	=	n T(1) + S(n) log₂(n).

(28)

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

Marc Moreno Maza
2007-01-10