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 $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).$$ (14)

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^2.$$ (15)

  
  
  We obtain:

  $$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).$$ (16)

  
  
  Hence we have:

  $$T(n) \in {\Theta}(n^2).$$ (17)

  
  

• Consider the relation:

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

  
  
  We obtain:

  $$T(n) \in {\Theta}({\log}_3(n) n).$$ (19)

  
  

A FORMULA TO ESTIMATE MATHEND000#. 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

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

$(2)$

if $a = 2$ then

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

$(3)$

if $a \geq 3$ then

$$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}).$$ (22)

Indeed

$$\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}$$ (23)

Moreover

$$\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}$$ (24)

Thus

$${\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.$$ (25)

Hence

$$T(2^p) \ \leq \ a^p \, T(1) + S(2^p) \, {\Sigma}_{j=0}^{j=p-1} \ {\left( \frac{a}{2} \right)}^j.$$ (26)

For $a = 1$ we obtain

$$\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}$$ (27)

For $a = 2$ we obtain

$$\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}$$ (28)