2
$\begingroup$

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.$

$\endgroup$
  • 1
    $\begingroup$ $k = \log_2\,n$ $\endgroup$ – DanielV Jun 15 '14 at 15:37
  • $\begingroup$ Here is a answer that does not use the Master Theorem. $\endgroup$ – Marko Riedel Jun 15 '14 at 18:30
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.