0
$\begingroup$

Consider the following recurrence relation:

$T(1) = 1$

$T(n) = 2T(\frac{n}{2}) + n$

I suspect that $T(n) = n + n\log_2 n$. Using mathematical induction, the base case holds since $T(1) = 1$. The inductive step seems a little complicated: how to prove $T(k+1)$ holds assuming $T(k)$ is true for $k\geq1$?

Any help is appreciated.

|cite|improve this question
$\endgroup$
  • $\begingroup$ This recurrence relation doesn't seem to tell you what, say, $T(3)$ is. $\endgroup$ – Fimpellizieri Nov 8 at 4:58
  • $\begingroup$ Perhaps induct on powers of $2$? I assume that's closer to what you're looking for since you have $\log_2(n)$ instead of a floor function there (since for $n \ne 2^a$ you'll definitely not get integers). $\endgroup$ – Eevee Trainer Nov 8 at 5:03
0
$\begingroup$

Another way to write your suspected formula is $T\left(2^k\right) = 2^k(k+1)$.

When $k=0$, we have $T(1) = 1$ so that's okay.

Now, assuming the formula holds for $k$, we would have by the recurrence relationship that

\begin{align} T\left(2^{k+1}\right) &= 2T\left(2^k\right) + 2^{k+1} \\&= 2\left(2^k(k+1)\right)+2^{k+1} \\&= 2^{k+1}(k+1)+2^{k+1} \\&= 2^{k+1}(k+2) \end{align}

which agrees with the suspected formula. So by induction, the suspected formula is correct.

Notice, however, that it is only defined for powers of $2$. This is because the recurrence relation itself is not defined for other integers.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Things are clearer now, but could you explain the first line of the inductive step, please? How do you know that $T(2^{k+1})=2T(2^k)+2^{k+1}$? $\endgroup$ – Mauricio Mendes Nov 8 at 5:15
  • $\begingroup$ This is the given recurrence relationship $T(n) = 2T(n/2) + n$. $\endgroup$ – Fimpellizieri Nov 8 at 5:16
  • $\begingroup$ Right, so you can use the inductive hypothesis. Thanks! $\endgroup$ – Mauricio Mendes Nov 8 at 5:18
  • $\begingroup$ You're welcome! Glad to have helped. $\endgroup$ – Fimpellizieri Nov 8 at 5:19

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.