The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+10 votes

Let $T(n)$ be the function defined by $T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$ for $n \geq 2$.

Which of the following statements is true?

  1. $T(n) = O \sqrt{n}$

  2. $T(n)=O(n)$

  3. $T(n) = O (\log n)$

  4. None of the above

asked in Algorithms by Veteran (59.8k points)
edited by | 783 views
How to do it by recurrence tree method?

Recursion Tree Method :-

Here , $\frac{n^{\frac{1}{2}}}{(\sqrt{2}-1 )} * [(2^{k})^{\frac{1}{2}}\sqrt{2} - 1]$

Now , put $k = lgn$

$\Rightarrow \frac{n^{\frac{1}{2}}}{(\sqrt{2}-1 )} * [(2^{lgn})^{\frac{1}{2}}\sqrt{2} - 1]$

$\Rightarrow \frac{n^{\frac{1}{2}}}{(\sqrt{2}-1 )} * [(n)^{\frac{1}{2}}\sqrt{2} - 1]$

So , here , $T(n) = \frac{\sqrt{2}}{(\sqrt{2}-1)}*n - \frac{n^{\frac{1}{2}}}{(\sqrt{2}-1)}$

$\Rightarrow T(n) \leqslant c*n , where \; c> 0$

So, $T(n) = O(n)$



each level cost should be same in recursion tree



@srestha It depends on recurrence.  Here it will not be same.  In the given link,  it will be same... 



why do u think cost of each level can be different?

these lines from cormen, which clearly told cost of each level be same


we add the costs across each level of the tree. The top level has total cost cn, the next level down has total cost cn/2+ c.n/2=cn, the level after that has total cost c.n/4+c.n/4+c.n/4+c.n/4= cn, and so on. In general, the level i below the top has 2i nodes, each contributing a cost of c.n=2i /, so that the ith level below the top has total cost $2^{i} c.(n/2^{i})= cn$. The bottom level has nnodes, each contributing a cost of c, for a total cost of cn.

The total number of levels of the recursion tree in Figure 2.5 is $lg n + 1$, where n is the number of leaves, corresponding to the input size. An informal inductive argument justifies this claim. The base case occurs when n = 1, in which case the tree has only one level. Since lg 1 = 0, we have that lg n + 1 gives the correct number of levels. Now assume as an inductive hypothesis that the number of levels of a recursion tree with 2i leaves is $lg2^{i}+1$=i+1(since for any value of i, we have that $lg2^{i} = i$. Because we are assuming that the input size is a power of 2, the next input size to consider is 2iC1. A tree with $n = 2^{i}+1$ leaves has one more level than a tree with 2i leaves, and so the total number of levels is.$(i + 1)+ 1 = lg 2^{i+1 } + 1.$

To compute the total cost represented by the recurrence (2.2), we simply add up the costs of all the levels. The recursion tree has lg n C 1 levels, each costing cn, for a total cost of cn.(lg n + 1)=cn lg n + cn. Ignoring the low-order term and the constant c gives the desired result of $\theta(n lg n)$



@srestha According to you what should be the same cost at each level here ?  In cormen,  it is given for a particular recurrence. 



I think it will be like this

$\left ( \sqrt{n} \right )$    ---------------------1st level

$\left ( \sqrt{n}/2 \right ),\left ( \sqrt{n}/2 \right )$--------------------in 2nd level

$\left ( \sqrt{n}/2^{2} \right ),\left ( \sqrt{n}/2^{2} \right ),\left ( \sqrt{n}/2^{2} \right ),\left ( \sqrt{n}/2^{2} \right )$----------in 3rd level


In last level it will be $ \left ( \sqrt{n}/2^{log_{2}\sqrt{n}} \right ) ,\left ( \sqrt{n}/2^{log_{2}\sqrt{n}} \right ),........\left ( \sqrt{n}/2^{log_{2}\sqrt{n}} \right )$

And there are $\left (2^{ {log_{2}\sqrt{n}}} \right )$ level

So, total time $\sqrt{n} .\left ( {2^{log_{2}\sqrt{n}}} \right ) =\Theta \left ( n \right )$

Is anything wrong here?


arey @srestha ma'am Aap kya kar rhi ho...Sorry , I am not getting you :( We have to replace n with n/2 each time, So, $\sqrt{n}$will be replaced with $\sqrt{n/2}$ not $\sqrt{n}/2$. If we have a recurrence as $T(n) = aT(\frac{n}{b}) + f(n)$ . Then cost at 1st level will be $f(n)$. Now on 2nd level, $T(n)$ calls $T(\frac{n}{b})$ 'a' times and cost of each call will be  $f(\frac{n}{b})$. So, total cost at 2nd level will be a* $f(\frac{n}{b})$. Now like this we go level by level.


but point is why u told

replaced with $\sqrt{n/2}$ not $\sqrt{n}/2$??

 In $f\left ( \frac{n}{b} \right )$

n and b two separate element ,right? they are not dependent

yes. n and b are separate element. If we have $f(x) = x^{2}$ then $f(\frac{x}{2}) = (\frac{x}{2})^{2}$. right ?

Same thing here. Initially we have f(n)= $\sqrt{n}$ at 1st level for T(n). Now T(n) calls T(n/2) '2' times. So, for each T(n/2) , cost will be f(n/2)... So, $f(\frac{n}{2}) = (\frac{n}{2})^{1/2}$ , not $(n^{1/2})/2$.

It is like Backward Substitution.

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

$T(n)$ $=$ $2[2T(n/2^{2}) + (n/2)^{1/2})] + \sqrt{n} = 2^{2}T(n/2^{2}) + 2(\frac{n}{2})^{1/2} + n^{1/2}$

where $2(\frac{n}{2})^{1/2} + n^{1/2}$ is the cost of first 2 levels.

1 Answer

+17 votes
Best answer

Answer is $B$.

using master method (case 1)

where a = 2, b = 2

O(n1/2) < O(nlogba)

O(n1/2) < O(nlog22)

answered by Loyal (8.8k points)
edited by

Related questions

0 votes
0 answers
asked Sep 29, 2014 in Non GATE by Kathleen Veteran (59.8k points) | 191 views
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,126 questions
53,252 answers
70,502 users