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'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?

---

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

---

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.

---

Is it really missed?

---

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

Please correct it.

---

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.