Solve the recurrence formally: $T(n) = 2T(n/2) +cn$

Question

I have a question. I've been googling a lot about these formal proofs of recurrences. I can solve this recurrence by drawing a recursive tree or using substition but when it comes to a formal proof, I have no idea what I have to prove and when do I know I'm done.

This is the recursive relation: $T(n) = 2T(\frac{n}{2}) + cn$ . After drawing a tree or using substition I guessed that it is $T(n) = \theta(nlgn)$ .

I have to prove this : $(\exists c_1,c_2 >0)(\exists n_0>0)(\forall n \geq n_0) ->c_1 nlgn \leq T(n) \leq c_2nlgn$

Answer 1

Solution 1

As I am not aware of standard methods to solve recurrences this self-made solution is pretty detailed (sorry for that).

EDIT: See the section "Extensions" for a compact solution using another method.

The recursion

$$T(n) = 2 T(\frac{n}{2}) + c \cdot n\tag{1}$$

can be solved explicitly as follows.

We assume that $n\to x$ is not confined to integers but is a positive real variable.

Letting $T(x) = x U(x) $ $(1)$ simplifies to

$$U(x) = U(\frac{x}{2}) +c \tag{2}$$

This is a linear inhomogenous functional equation.

The general solution is the sum of the general solution of the homogenous equation and a special solution of the inhomogenous equation.

The homgeneous equation is

$$U_{h}(x) = U_{h}(\frac{x}{2})\tag{3}$$

It is easily solved: because $(3)$ holds for all $x\ge 0$ we must have

$$U_{h}(x) = A \tag{4}$$

with some constant $A$.

In order to find a special solution of $(2)$ we "vary" the constant letting $A\to A(x)$ so that $(2)$ becomes

$$A(x)=A(x/2)+c\tag{5}$$

Since we need only a special solution we can set $A(1) = 0$ so that

$$A(2) = c $$ $$A(4) = A(2) + c = 2 c$$ $$A(8) = A(4) + c = A(2) + 2 c= 3 c$$ $$...$$ $$A(2^k) = k c$$

with $x = 2^{k}$ or $k = \frac{\log(x)}{\log(2)}$ we have the solution

$$U_{i}= A(x) = c \frac{\log(x)}{\log(2)}\tag{6}$$

and finally the general solution becomes

$$T(x) = U_{h}+ U_{i} = B x + c x \frac{\log(x)}{\log(2)}\tag{7}$$

with some arbitrary constant $B$.

Extension

Let us study the equation

$$T(x) = a T(\frac{x}{b}) + h(x)\tag{e1}$$

where $a,b>0$ and $h(x)$ is some "reasonable" function.

The key idea now is to transform the variables letting

$$x = b^t, t=\frac{\log(x)}{\log(b)}, T(b^t) = g(t), h(b^t) = p(t)\tag{e2}$$

so that $(e1)$ becomes

$$g(t) = a g(t-1) + p(t)\tag{e3}$$

which is a common linear inhomogenous recursion of first order.

The solution is easily found to be

$$g(t) = a^t g(0) + \sum_{k=0}^{t-1} a^k p( (t-k))\tag{e4}$$

Finally, inverting $(e2)$ and setting the constant $g(0) \to A$, we get

$$T(x) = A x^{\frac{\log(a)}{\log(b)}}+ \sum_{k=0}^{\frac{\log(x)}{\log(b)}-1} a^k h(b^{ \frac{\log(x)}{\log(b)}-k})\tag{e5}$$

Discussion

1) It is interesting that the resulting function $T(x)$ of the product recurrence relation $(1)$ (sorry for coining this term) is almost always a real number and not an integer.

This is in contrast to difference recurrence relations like $(e3)$ where we can very well have integers as solutions.

2) The homogenous equation $(e1)$, i.e. with $h=0$, can be solved immediately with the Ansatz $T(x) = x^\alpha$ which leads to $x^{\alpha} = a (\frac{x}{b})^{\alpha }$ from which we find $\alpha = \frac{\log(a)}{\log(b)}$ in agreement with $(e5)$.

Answer 2

Solution 2

This alternative solution uses calculus.

The recurrence

$$f(x) = 2 f(\frac{x}{2}) + c x\tag{1}$$

will be differentiated with respect to $x$ as often as is necessary to get a homogenous equation.

In this case we need the second derivative.

For the first derivative $g(x) = f'(x)$ we get

$$g(x) = g(\frac{x}{2})) + c\tag{2}$$

for the second derivative $h(x) = g'(x) = f''(x)$ we have

$$h(x) = \frac{1}{2} h(\frac{x}{2}))\tag{3}$$

Letting $h(1)=A$ from $(3)$ we generate the seqence

$$h(2) = A \frac{1}{2} $$ $$h(4) = A \frac{1}{2} h(2) =A \frac{1}{2^2} $$ $$...$$ $$h(2^k) = A \frac{1}{2^k} $$

or, with $x=2^k$, we have found the simple result that

$$h(x) = \frac{A}{x}\tag{4}$$

Now we have to reverse the derivatives.

From

$$g'(x) = h(x) = \frac{A}{x}$$

we get by integrating

$$g(x) = A \log(x) + B\tag{5}$$

Inserting this into $(2)$ gives

$$ A \log(x) + B = A \log(\frac{x}{2}) + B+ c=A \log(x) -A \log(2)+ B+ c$$

from which we find that

$$A = \frac{c}{\log(2)}$$

and

$$g(x) = \frac{c}{\log(2)} \log(x) + B\tag{5a}$$

Now the final integration, using $\int \log (x) \, dx= - x + x \log(x)$, gives

$$f(x) = B x + \frac{c}{\log(2)} (-x + x \log(x)) + C$$

From $(1)$ we have $f(x\to0)=0$, hence $C=0$ and finally (with a redfined constant $B$) we arrive at the solution of $(1)$

$$f(x) = B x + c\; \frac{ x \log(x)}{\log(2)}\tag{6}$$

in agreement with solution 1.