why we are getting different answer with master's formula.

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

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

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

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

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