Complexity of $T(n) = 2T(n/2) + n$

Question

How can I prove that $T(n) = 2T(n/2) + n$ is $\mathcal{O}(n \, \log{n})$ without master theorem , if $T(1)=\mathcal{O}(1)$?

How can I continue from here?

$T(n) = 2T(n/2) + n,$
$T(n) = 4T(n/4) + 2n,$
$T(n) =$ $...,$
$T(n) = 2^kT(n/2^k) + kn.$

Answer 1

The # of recurrences until $T(\frac{n}{2}) = T(1)$ is $log_2(n)$ so simply substitute $k$ with $log_2(n)$ from $T(n) = 2^kT(\frac{n}{2^k})+kn$ to get a simplified result.

As for how the # of recurrence is $log_2(n)$, where each recurrence halves $n$, note that this has an inverse relationship to doubling $n$ at each recurrence:

Starting at 1, you need to double this $log_2(n)$ many times in order to get up to $n$: $1*2^{log_2(n)} = n$. Conversely, starting at $n$, you need to halve this $log_2(n)$ many times in order to get down to 1: $\frac{n}{2^{log_2(n)}} = 1$

This remains true for the case where $T(n) = 2T(n/2) + O(n)$, which is useful for such divide-and-conquer algorithm.

Answer 2

Note that $$\frac{T(n)}n=\frac{T(n/2)}{n/2}+1 $$ hence $$\frac{T(2^k)}{2^k}=T(1)+k$$ that is, $$ T(2^k)\in\Theta(k\,2^k). $$ It seems that, in the context of homework on complexity of algorithms, the (rigorous) result above is considered to imply (although, in the absence of some supplementary hypothesis, it does not) that $$ T(n)\in\Theta(n\,\log n). $$

Answer 3

Use substitution

$$S(n) = T(2^n) =2T(\frac{2^n}2)+2^n = 2T(2^{n-1})+2^n = 2S(n-1)+2^n $$

So you have to solve recursion

$$S(n) = 2S(n-1) + 2^n,$$

or

$$S(n)-2S(n-1) = 2^n.$$

So,

$$S(n-1) - 2S(n-2) = 2^{n-1}$$

and

$$2S(n-1) - 4S(n-2) = 2^n$$

So,

$$S(n) - 2S(n-1) = 2S(n-1)-4S(n-2)$$

or

$$S(n) - 4S(n-1)+4S(n-1) = 0.$$

Characteristic equation for the recursion is

$$x^2-4x+4 = 0,$$

or

$$(x-2)^2 = 0.$$

This equation has troots $x_1 = x_2 = 2$, so general solution for it is

$$S(n) = C_12^n + C_2n2^n.$$

At the end you turn back to $T(n)$.

$$T(n) = S(\lg n) = C_1n + C_2n\lg n$$

From the last equation you can conclude that

$$T(n) = \Theta(n\lg n).$$

Answer 4

You can assume the inductive hypothesis that $T(n)=Cn + nlogn$, where $T(1)=C$ and then proceed to prove this result easily by induction. Then, the result is clear. Note that this proves the result only for powers of two but you can use asymptotics to generalise this result for all $n$.