search
Log In
4 votes
1.8k views
How to solve above recurrence relation?
in Algorithms 1.8k views

2 Answers

6 votes
$T(n) = \sqrt{2} T(\frac{n}{2}) + n^{\frac{1}{2}}$    .............. (1)

$T(\frac{n}{2}) = \sqrt{2} T(\frac{n}{4}) + (\frac{n}{2})^{\frac{1}{2}}$         ..........(2)

$T(\frac{n}{4}) = \sqrt{2} T(\frac{n}{8}) + (\frac{n}{4})^{\frac{1}{2}}$         ........(3)

Resubstituting (3) in (2)

$T(\frac{n}{2}) = \sqrt{2} [\sqrt{2} T(\frac{n}{8}) + (\frac{n}{4})^{\frac{1}{2}}] + (\frac{n}{2})^{\frac{1}{2}}$

$T(\frac{n}{2}) = 2T(\frac{n}{8}) + (\frac{n}{2})^{\frac{1}{2}} + (\frac{n}{2})^{\frac{1}{2}}$   ..........(4)

Resubstituting (4) in (1)

$T(n) = 2\sqrt{2}T(\frac{n}{8}) +n^{\frac{1}{2}} + n^{\frac{1}{2}} + n^{\frac{1}{2}}$ .........(5)

Now $n = 2^k$ hence $k = logn$

Generalizing eq (5)...

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

By solving the above equation,

$T(n) = 2^{\frac{1}{2}logn} + logn (\sqrt{n})$             .........assuming $T(\frac{n}{2^k}) = T(1) = 1$

$T(n) = \sqrt{n} + logn(\sqrt{n})$

Hence $T(n) = \sqrt{n}(logn + 1)$

edited by
0
why we are getting different answer with master's formula.
1

@anoop
Bcoz the question you asked is different from actual gate question.
There it asked evaluates to (exact equation is needed) , buy masters theorem gives approximate asymptotic upper bound.
https://gateoverflow.in/3354/gate2008-it-44

4 votes
From master theorem case 2

here a = √2 , b = 2 , k=1/2, p = 0

a = b^k which is true

p > -1

So complexity is theta(n^(log a base to b) log^(p+1)n).

theta(√n logn).
0
but the answer is  sqrt(n) (logn+1). It is a question from made easy prev. year question [year 2008 2 marks] page no 370 qno 32.
0
#anoop
Bcoz the question you asked is different from actual gate question.
There it asked evaluates to (exact equation is needed) , buy masters theorem gives approximate asymptotic upper bound.
https://gateoverflow.in/3354/gate2008-it-44

Related questions

3 votes
2 answers
1
3k views
T(n) = sqrt(n) * T(sqrt(n)) + n Given solution is O(log log n). But my solution is O(n log log n). 'wolframalpha'' shows the answer same as mine. You can find the solution here. Can anyone confirm the solution and provide an explantion?
asked Nov 22, 2018 in Algorithms gmrishikumar 3k views
8 votes
1 answer
2
3.7k views
How to solve above recurrence relation (With substitution method)??
asked Jan 8, 2018 in Algorithms anoop yadav 2 3.7k views
2 votes
4 answers
3
1.9k views
I've been struggling to come to exact solution for this. Master's theorem is not applicable and likely way to get to answer is Recursion tree. Which is giving me Theta(n) as an answer. Steps : => 1) T(n) = 2T(n/4) + √3 2) Emerging Pattern => (1/2^k) * n 3) Considering ... + n/4 + ..... = n/2 Which is incorrect , Answer given is ( √n log n ) , would appreciate if someone could shed light how so ?
asked Oct 11, 2016 in Algorithms vishal8492 1.9k views
4 votes
2 answers
4
...