Question

Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence:\[T(n) = 2 \ \ if\ \ n = 2\]\[2T(n/2)+n\ \ \ \ if\ \ \ n = 2^k,\ \ \ for\ \ k > 1\]
is T(n) = nlg(n)

Answer 1

T(n) is what?

Answer 2

nlog(n) ?

Answer 3

\(nlog_2(n)\)

Answer 4

Base 2 I guess?

Answer 5

you can prove it without using induction

Answer 6

I want to prove the relation for \(2^n\), \(n\ge 1\) using induction:
First for n=1, \(T(2^1)=2=2\log_{2}(2)\).
Now, assume the relation is true for n=k, that is:
\[T(2^k)=2^k\log_{2}(2^k)=k\cdot2^k\]
Lets show that this assumption implies that it's also true for n=k+1:
\[T(2^{k+1})=2T(\frac{2^{k+1}}{2})+2^{k+1}=2T(2^k)+2^{k+1}=2k\cdot2^k+2^{k+1}\]
\[=(k+1)2^{k+1}=2^{k+1}\log_{2}(2^{k+1}). ■\]

Answer 7

\[\begin{align}
\text{if } T(n) &= n\log_2(n)\\
\text{then } T(n/2) &= \frac{n}{2}\log_2(\frac{n}{2})\\
&=\frac{n}{2}(\log_2(n)-\log_2(2))\\
&=\frac{n}{2}(log_2(n)-1)\\
\therefore 2T(n)&=n\log_2(n)-n\\
&=T(n)-n\\
\therefore T(n)&=2T(n/2)+n
\end{align}\]

Answer 8

3rd from last line was wrong on left hand side - should be 2T(n/2)=

Answer 9

and this seems to have no restriction of \(n=2^k\) on it

Answer 10

have I made a mistake somewhere?