The Gateway to Computer Science Excellence

+9 votes

Best answer

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

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

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

$(\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.

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,357 answers

198,484 comments

105,256 users