844 views
Find a solution to the following recurrence equation:

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

$T(1)=1$
| 844 views

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

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

$\ldots = \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$
by Veteran (431k points)
selected by
0
it's not mentioned in the question that n is a power of 2 and they have not used ceil or floor for n/2, how can we assume that it will reach t(1)? shouldn't we find a bound for this then?
0
For anyone wondering how that last step with $(1/\sqrt{2})^{lgn + 1} = 1/(\sqrt{2*n})$ happened,

$(\frac{1}{\sqrt{2}})^{lgn} = 2^{-\frac{1}{2}.lgn} = x$ => equation 1.

Take logarithm of both sides -:

$lgn . lg(1/\sqrt{2}) = lgx$

Then write as a power of 2 and take the power out.

$lgn.lg(2)^{-1/2} = lgx$

$lgx = \frac{-1}{2}.lgn$ => equation 2.

$-2.lgx = lgn$

Raise to a power of 2 to get $n$ as it is.

$2^{-2.lgx} = 2^{lgn} = n$

$\sqrt{n} = 2^{-lgx}$

Using equation 2 here to replace $lgx$,

$\sqrt{n} = 2^{+\frac{1}{2}.lgn}$

But the RHS of this is $\frac{1}{x}$, from equation 1, which we set out to find.

So $x = \frac{1}{\sqrt{n}}$.
0

Also, @Arjun sir, you might have missed $T(1)$ at the end. I think there will be a $+1$ in the final answer that is not being accounted for.

@Aayush Tripathi for such questions you can assume that $n$ is a power of 2, or else the solution becomes a little complicated. The answer is assuming that $n$ is a power of 2.

0
Is it really missed?
0
Yes you missed +1 and even it is √2^logn -1 but you have written only √2^logn.

+1

It is correct, as because here in the 3rd line it has been assumed that $n=2^k \Rightarrow k=log n$,

So the last two terms of the 3rd line i.e. $\sqrt{n/2^{log n -1}}+T(1)=\sqrt{n/2^{k-1}}+1$

$=\sqrt{n/2^{k-1}}+\sqrt{n/2^{k}}$ as because $n=2^k$

$\Rightarrow\sqrt{n/2^{log n-1}}+\sqrt{n/2^{log n}}$ Hence the GP series has been taken as sum of $log n +1$ terms.

0
That makes it much clearer, I had not understood how that change had happened. Thanks!

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

by Active (3.1k points)
edited by
+2

Last Steps

0
Nice explanation, but we can solve this using Master's Theorem which can solve a lot of time in exam
+5

@ we have to find a soln to this recurrence ,not time complexity

0
thanks
–1 vote
a < b^k

case 3a:  n^(1/2)*log^(0) = n^(1/2)
by Active (3.8k points)
–1
is it correct answer or not ???