edited by
4,159 views

3 Answers

Best answer
26 votes
26 votes
$T(n) = T(\frac{n}{2})+ \sqrt n$

$\quad = T(\frac{n}{4}) + \sqrt n + \sqrt {(n/2)}$

$\quad \vdots$

$\quad = \sqrt n + \sqrt {(n/2)}+\sqrt {(n/4)}+\sqrt {(n/8)}+\ldots + \sqrt{(n/2^{\lg n-1})} + T(1)$

$ \quad = \sqrt n \left[ 1+\frac{1}{\sqrt 2} + \frac{1}{{\sqrt 2}^2} + \ldots + \frac{1}{\sqrt 2^{{\lg n}}}\right]$

$\quad = \sqrt n \left[ \frac{1 - (\frac{1}{\sqrt 2})^{\lg n+1}}{1-\frac{1}{\sqrt 2}}\right]$ (Sum of $\lg n +1$ terms of GP with $a = 1$ and $r = 1\sqrt 2)$

$\quad = \sqrt n \left[ \frac{1 - \frac{1}{\sqrt 2\sqrt n}}{1 - \frac{1}{\sqrt 2}}\right]$

$\quad =  \frac{\sqrt {2n} -1}{\sqrt 2 - 1}$

$\quad =  \left({\sqrt {2n} -1}\right)\left({\sqrt 2 + 1}\right)$

$\quad = \sqrt n \left(2+\sqrt 2\right)-\sqrt 2-1$
edited by
23 votes
23 votes

Solution of the Recurrence is

 

$T(n) = \sqrt{n} + \left(\dfrac{n}{2} \right)$

$T(1) = 1$

$T(n) = T\left(\dfrac{n}{2}\right) + \left(n\right)^{\frac{1}{2}}$

$T(n) = \left[T\left(\dfrac{n}{2^{2}}\right) + \left(\dfrac{n}{2}\right)^{\frac{1}{2}}\right] + \left( n \right)^{\frac{1}{2}}$

$T(n) = T\left(\dfrac{n}{2^{3}}\right) + \left(\dfrac{n}{2^{2}}\right)^{\frac{1}{2}} + \left(\dfrac{n}{2}\right)^{\frac{1}{2}} + \left( n \right)^{\frac{1}{2}}$


$T(n) = T\left(\dfrac{n}{2^{k}}\right) + \left(\dfrac{n}{2^{k-1}}\right)^{\frac{1}{2}} + \left(\dfrac{n}{2^{k-2}}\right)^{\frac{1}{2}} + \left(\dfrac{n}{2^{k-3}}\right)^{\frac{1}{2}} + \cdot\cdot\cdot + \left( \dfrac{n}{2} \right)^{\frac{1}{2}} + \left(n \right)^{\frac{1}{2}} $

$\implies$ when $\dfrac{n}{2^{k}} = 1$

$\implies 2^{k} = n \implies k = \log_{2}n$

$T(n) = T(1) + \left(\dfrac{n}{2^{k}\cdot 2^{-1}}\right)^{\frac{1}{2}} + \left(\dfrac{n}{2^{k}\cdot2^{-2}}\right)^{\frac{1}{2}} + \left(\dfrac{n}{2^{k}\cdot2^{-3}}\right)^{\frac{1}{2}} + \cdot\cdot\cdot + \left( \dfrac{n}{2} \right)^{\frac{1}{2}} + \left(n \right)^{\frac{1}{2}} $

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

$T(n) = 1 + \left(2\right)^{\frac{1}{2}} + \left(2^{2}\right)^{\frac{1}{2}} + \left(2^{3}\right)^{\frac{1}{2}} + \cdot\cdot\cdot + \left(n\right)^{\frac{1}{2}}$

$T(n) = 2^{0} + \left(2\right)^{\frac{1}{2}} +  2 + \left(2 \right)^{\frac{3}{2}} + \cdot\cdot\cdot +\log_{2} n  \ \ \text{times}  + \sqrt{n}$

$T(n) = \dfrac{\left(\sqrt{2}\right)^{\log_{2}n} - 1}{\left(\sqrt{2} - 1\right)}  + \sqrt{n}$

$T(n) = \dfrac{2 ^{\log_{2}n^{\frac{1}{2}}} - 1}{\sqrt{2} - 1}  + \sqrt{n}$

$T(n) = \dfrac{\sqrt{n} - 1}{\sqrt{2} - 1}  + \sqrt{n}$

edited by
0 votes
0 votes
a < b^k

case 3a:  n^(1/2)*log^(0) = n^(1/2)

Related questions

7 votes
7 votes
2 answers
1
makhdoom ghaya asked Dec 15, 2016
2,596 views
A language uses an alphabet of six letters, $\left\{a, b, c, d, e, f\right\}$. The relative frequency of use of each letter of the alphabet in the language is as given be...
12 votes
12 votes
4 answers
4
makhdoom ghaya asked Nov 30, 2016
2,655 views
In the graph shown above, the depth-first spanning tree edges are marked with a $’ T’$. Identify the forward, backward, and cross edges.