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

@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

Comments

@theradash u can use $fx$  for functions  to  make ur ans good use latex equations