
MHB Master
#1
February 25th, 2015,
16:13
Hello!!!
Use induction to show that if $n$ is a power of $2$ then the solution of the recurrence relation
$$\left\{\begin{matrix}
2 &, \text{ if } n=2 \\
2T\left( \frac{n}{2} \right )+n & , \text{ if } n=2^k, \text{ for } k>1
\end{matrix}\right.$$
is $T(n)=n \lg n$.
That's what I have tried:
We will use induction on $k$ to show that $T(2^k)=2^k \cdot k$.
For $k=1 \Rightarrow n=2^1=2$ we have: $T(2)=2=2 \lg 2 \checkmark$.
We suppose that for some $k \geq 1$ it holds that $T(2^k)=2^k \cdot k$.
For $k+1$: $T(2^{k+1})=2T\left( \frac{2^{k+1}}{2} \right )+2^{k+1}=2T(2^k)+2^{k+1} \overset{\text{induction hypothesis}}{=}2 \cdot 2^k \cdot k+2^{k+1}=2^{k+1} \cdot k+2^{k+1}=2^{k+1}(k+1)$.
Thus, $\forall k \in \mathbb{N}$ it holds that $T(2^k)=2^k \cdot k$.
Could you tell me if my formulation is right or if I could improve something?

February 25th, 2015 16:13
# ADS
Circuit advertisement

زيد اليافعي
#2
February 25th, 2015,
18:03
Originally Posted by
evinda
Hello!!!
Use induction to show that if $n$ is a power of $2$ then the solution of the recurrence relation
$$\left\{\begin{matrix}
2 &, \text{ if } n=2 \\
2T\left( \frac{n}{2} \right )+n & , \text{ if } n=2^k, \text{ for } k>1
\end{matrix}\right.$$
is $T(n)=n \lg n$.
That's what I have tried:
We will use induction on $k$ to show that $T(2^k)=2^k \cdot k$.
For $k=1 \Rightarrow n=2^1=2$ we have: $T(2)=2=2 \lg 2 \checkmark$.
We suppose that for some $k \geq 1$ it holds that $T(2^k)=2^k \cdot k$.
For $k+1$: $T(2^{k+1})=2T\left( \frac{2^{k+1}}{2} \right )+2^{k+1}=2T(2^k)+2^{k+1} \overset{\text{induction hypothesis}}{=}2 \cdot 2^k \cdot k+2^{k+1}=2^{k+1} \cdot k+2^{k+1}=2^{k+1}(k+1)$.
Thus, $\forall k \in \mathbb{N}$ it holds that $T(2^k)=2^k \cdot k$.
Could you tell me if my formulation is right or if I could improve something?
Looks fine for me

MHB Master
#3
February 25th, 2015,
18:06
Thread Author
Originally Posted by
ZaidAlyafey
Looks fine for me
Would it be better to say at the beginning something like that?
We want to show that when $n$ is some power of $2$ then the solution of the recurrence relation is $T(n)=n \lg n$, i.e. that for $n=2^k$ where $k$ is some positive integer the solution is equal to $2^k \cdot k$.
Last edited by evinda; February 25th, 2015 at 18:13.

زيد اليافعي
#4
February 26th, 2015,
07:58
Originally Posted by
evinda
Would it be better to say at the beginning something like that?
We want to show that when $n$ is some power of $2$ then the solution of the recurrence relation is $T(n)=n \lg n$, i.e. that for $n=2^k$ where $k$ is some positive integer the solution is equal to $2^k \cdot k$.
Yeah, it is better.