Awesome q2a theme

0 votes

+4 votes

Best answer

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

After substituting $T(n/2)$, i.e. 1st substitution:

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

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

After substituting $T(n/2^2)$, i.e. 2nd substitution:

$T(n) = 2^2*(2*T(\frac{n}{2^3})+(\frac{n}{2^2})^\frac{1}{2})+n^\frac{1}{2}*(2^\frac{1}{2}+1)$

$ = 2^3*T(\frac{n}{2^3})+n^\frac{1}{2}*(2^\frac{2}{2}+2^\frac{1}{2}+1)$

Hence after $k$ substitutions, we get:

$T(n)=2^{k+1}*T(\frac{n}{2^{k+1}})+n^\frac{1}{2}*(2^\frac{k}{2}+\dots\ 2^\frac{2}{2}+2^\frac{1}{2}+1)$

Right part has a sum of GP with common ratio $2^\frac{1}{2}$, first term $1$ and total $k+1$ terms (i.e. $2^\frac{0}{2}$ to $2^\frac{k}{2}$), the value of this sum will be:

$\frac{2^\frac{k+1}{2}-1}{2^\frac{1}{2}-1}=\frac{2^\frac{k+1}{2}-1}{0.414}$, put this value in the relation.

$\implies T(n)=2^{k+1}*T(\frac{n}{2^{k+1}})+n^\frac{1}{2}*\frac{2^\frac{k+1}{2}-1}{0.414}$

Now, $\frac{n}{2^{k+1}}=1$

$\implies n=2^{k+1}$

$\implies k+1=\log{n}$

Using this, we get:

$T(n)=n*T(\frac{n}{n})+n^\frac{1}{2}*\frac{2^\frac{\log{n}}{2}-1}{0.414}$

$\implies T(n)=n*T(1)+n^\frac{1}{2}*\frac{n^\frac{1}{2}-1}{0.414}$

$\implies T(n)=n*1+\frac{n-n^\frac{1}{2}}{0.414}$

Ignore constants:

$T(n)=O(n+n-n^\frac{1}{2})$

Ignore lower order terms and constants,

Hence, $T(n)=O(n)$

After substituting $T(n/2)$, i.e. 1st substitution:

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

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

After substituting $T(n/2^2)$, i.e. 2nd substitution:

$T(n) = 2^2*(2*T(\frac{n}{2^3})+(\frac{n}{2^2})^\frac{1}{2})+n^\frac{1}{2}*(2^\frac{1}{2}+1)$

$ = 2^3*T(\frac{n}{2^3})+n^\frac{1}{2}*(2^\frac{2}{2}+2^\frac{1}{2}+1)$

Hence after $k$ substitutions, we get:

$T(n)=2^{k+1}*T(\frac{n}{2^{k+1}})+n^\frac{1}{2}*(2^\frac{k}{2}+\dots\ 2^\frac{2}{2}+2^\frac{1}{2}+1)$

Right part has a sum of GP with common ratio $2^\frac{1}{2}$, first term $1$ and total $k+1$ terms (i.e. $2^\frac{0}{2}$ to $2^\frac{k}{2}$), the value of this sum will be:

$\frac{2^\frac{k+1}{2}-1}{2^\frac{1}{2}-1}=\frac{2^\frac{k+1}{2}-1}{0.414}$, put this value in the relation.

$\implies T(n)=2^{k+1}*T(\frac{n}{2^{k+1}})+n^\frac{1}{2}*\frac{2^\frac{k+1}{2}-1}{0.414}$

Now, $\frac{n}{2^{k+1}}=1$

$\implies n=2^{k+1}$

$\implies k+1=\log{n}$

Using this, we get:

$T(n)=n*T(\frac{n}{n})+n^\frac{1}{2}*\frac{2^\frac{\log{n}}{2}-1}{0.414}$

$\implies T(n)=n*T(1)+n^\frac{1}{2}*\frac{n^\frac{1}{2}-1}{0.414}$

$\implies T(n)=n*1+\frac{n-n^\frac{1}{2}}{0.414}$

Ignore constants:

$T(n)=O(n+n-n^\frac{1}{2})$

Ignore lower order terms and constants,

Hence, $T(n)=O(n)$

8,437 questions

2,714 answers

13,238 comments

95,460 users