GATE CSE 1989 | Question: 13b

Question

Find a solution to the following recurrence equation:

• $T(n)=\sqrt{n}+T\left(\frac{n}{2}\right)$
• $T(1)=1$

Answer 1

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

Comments

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.

---

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

---

@pritishc, you can directly multiply and get that.

$2^{^{-1/2}*(logn+1)}=2^{^{-1/2(logn)}}*2^{-1/2}=2^{log(n^{-1/2})}*1/\sqrt{2}=1/\sqrt{n}*1/\sqrt{2}$

Answer 2

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

Comments

Last Steps

---

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

---

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

---

thanks

Answer 3

a < b^k

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

Comments

is it correct answer or not ???

---

No this is not correct bcoz we have to find the solution not the timecomplexity of recurence

---

This is correct asymptotic bound of the given recurrence relation but it's not the solution of the recurrence relation.

Answer 4

Using Master Theorem,

n^log1   ??   n^1/2

1         <    n^1/2

 

So. T. C=O(√n)

 

 

Comments

This has to be kept in mind