Awesome q2a theme
0 votes
57 views
T(n) = 2*T(n/2) + sqrt(n) ; n >=2

       =  1; otherwise
in Algorithms by (7 points) | 57 views
0

I have seen this before but I was not able to solve it further. I am uploading the image where I am stuck. 

 

0
k = log n so 2^k = n

seq like n+n/root(2)+n/root(4)+….1 = n

you done right now put the value of n every where you see root(2^k-1  * 2^k) = 2^k (1/root(n))
0
If you don't mind, could you post the solution for this? I am having trouble while solving this.

1 Answer

+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)$
by (861 points)
selected by
0
Thank you so much for the efforts you put in.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,647 questions
2,855 answers
13,739 comments
95,564 users