1

I'm trying to figure out this recursive problem with induction, and I'm at a loss as to how I'm supposed to make $T(n+1) = n\log n$ , like it it wasn't $n+1$, I could do it but from what I read about induction we have to make it equal to $n\log n$. Usually I find what's in the parenthesis so $T(1)$ $T(n/2)$ but $(n+1)$. I'm not sure how to start.

I've tried watching videos on it but I get stuck at $T(n+1) = 2T(n+1/2)+n+1$. I've seen some people on stack do it but none of them use $T(n+1)$ but I thought induction we had to make sure $(Tn+1) = n\log n$ (or whatever you're trying to prove).

$T(n) = \begin{cases} 0 & n=1 \\ 2T(n/2)+n & n>1\end{cases}$

Prove $T(n) = O(n\log n)$ using induction.

angryavian
  • 89,882
Mitch
  • 11
  • 3
    And I suppose there is a convention to use for $T(n/2)$ when $n$ is odd? You should probably include a link for the definitions used in this type of notation. – GEdgar Mar 07 '22 at 22:20
  • 1
    Is this not a direct application of the master theorem? – angryavian Mar 07 '22 at 22:33
  • You need to use the induction hypothesis to eliminate the $2T((n+1)/2)$ term. You may need to prove that there is a relationship between $T(n+1)$ and $T((n+1)/2)$ first to do so. Note that when you're only trying to bound things statements like $\log n \leq n$ or $n/2 < n$ can lead to simplifications. – CyclotomicField Mar 07 '22 at 22:36
  • @angryavian I'm not sure it would count as a proof by induction if they invoked the master theorem. – CyclotomicField Mar 07 '22 at 22:38
  • If you are dead set on using induction on $n$ to $n+1$ - let $S(k) = T(2^k)$. Then $S(k) = 2S(k-1) + 2^k$ and now you can translate between the two. – user525966 Mar 07 '22 at 22:38

1 Answers1

1

Suppose $T(n) \le C n \log n$ for a fixed $n$ and some $C > 0$. Without loss of generality we can assume $C \ge 2$. Then, $$T(2n) = 2T(n) + 2n \le 2C n \log n + 2 n \le C \cdot 2n \left(\log (n) + \frac{1}{2}\right) \le C \cdot 2n \log (2n).$$

angryavian
  • 89,882