edited by
5,525 views

2 Answers

7 votes
7 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
6 votes
6 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).

Related questions

0 votes
0 votes
1 answer
1
4 votes
4 votes
2 answers
2
gmrishikumar asked Nov 22, 2018
11,405 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...
0 votes
0 votes
1 answer
3
lucasbbs asked Feb 28, 2022
6,575 views
How do I apply the master theorem in the above recurrence? Please give details about which case and on hiow to solve the asymptotic analysis...
4 votes
4 votes
1 answer
4
Sanjay Sharma asked May 26, 2016
18,591 views
the solution of recurrence relationT(n)=2T(floor(sqrt(n))+log n