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 = b^p. 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.

• Consider the relation:

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

  
  
  We obtain:

  $${\frac{{n^2}}{{2}}} {\frac{{n^2}}{{4}}} {\frac{{n^2}}{{8}}} {\frac{{n^2}}{{2^p}}}$$ (15)

  
  
  Hence we have:

  $$\in \Theta$$ (16)

  
  

• Consider the relation:

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

  
  
  We obtain:

  $$\in \Theta$$ (18)

  
  

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 = 2^p then T(n)  $\leq$   a T(n/2) + S(n).

Then for n = 2^p we have

(1)

if a = 1 then

$$\leq \in \cal {O}$$ (19)

(2)

if a = 2 then

$$\leq \in \cal {O}$$ (20)

(3)

if a $\geq$ 3 then

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

Indeed

T(2p)	$$\leq$$	a T(2p-1) + S(2p)
	$$\leq$$	a$$\left[\vphantom{ a \, T(2^{p-2}) + S(2^{p-1}) }\right.$$a T(2p-2) + S(2p-1)$$\left.\vphantom{ a \, T(2^{p-2}) + S(2^{p-1}) }\right]$$ + S(2p)
	=	a2 T(2p-2) + a S(2p-1) + S(2p)
	$$\leq$$	a2$$\left[\vphantom{ a \, T(2^{p-3}) + S(2^{p-2}) }\right.$$a T(2p-3) + S(2p-2)$$\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)
	$$\leq$$	ap T(1) + $$\Sigma_{{{j=0}}}^{{{j=p-1}}}$$ aj S(2p-j)

(22)

Moreover

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

(23)

Thus

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

Hence

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

For a = 1 we obtain

T(2p)	$$\leq$$	T(1) + S(2p) $$\Sigma_{{{j=0}}}^{{{j=p-1}}}$$ $$\left(\vphantom{ \frac{1}{2} }\right.$$$${\frac{{1}}{{2}}}$$$$\left.\vphantom{ \frac{1}{2} }\right)^{{j}}_{{}}$$
	=	T(1) + S(2p) $${\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)	$$\leq$$	2p T(1) + S(2p) p
	=	n T(1) + S(n) log2(n).

(27)