# t(n) = sqrt(2) t(n/2) + sqrt(n)

1.8k views
How to solve above recurrence relation?

$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
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

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

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?