GATE CSE 1997 | Question: 4.6

Question

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?

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

• B. $T(n)=O(n)$

• C. $T(n) = O (\log n)$

• D. None of the above

Comments

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

---

@ankitgupta.1729

each level cost should be same in recursion tree

right?

https://gateoverflow.in/1325/gate2009-39

---

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

---

@ankitgupta.1729

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. 

---

@ankitgupta.1729

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.

---

@ankitgupta.1729

@srestha

using floor or ceil make any difference in big O notation?

Asking not for this question but in general scenario does floor or ceil make any change in overall complexity?

 

---

@jlimbasiya  

No.

---

@ankitgupta.1729

You resolved all my doubts on solving the method by recursion tree method. Earlier I also think that cost of each level is same but when i tried to solve some question by taking this, few questions I’m not able to solve but now i understand what is the reason behind it...😊

 

Answer 1

Answer is $B$.

using master method (case 1)

where a = 2, b = 2

O(n^1/2) < O(n^log_ba)

O(n^1/2) < O(n^log₂2)

Comments

Here $\mathrm{k \ngeq 0}$, then how you applied Master's theorem?

---

@Satbir

Do you think this selected answer even correct?

---

k is 0.5

---

Ohh..that was a foolish mistake.

Thanks.

Answer 2

n^(log2 2)=n

f(n)=√n

n^(log2 2) is polynomially greater then f(n)

Extended Master's theorm CASE 1:

f(n)=O(n^(logb a)-e) e>0,then T(n)=Θ(n^logb a)

T(n)=Θ(n) Option B