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.