Quiz question

Question

Given the tight asymptotic bound for the recurrence equation :

T(n) = 2T($\frac{n }4{}$) + 1

 

1. O(√ n)
2. Ω(√ n)
3. θ(√ n)
4. O(n^2)

 

Using master’s theorem, the result comes to be θ(√ n). Thus option A,B,C are definitely correct.

According to the solutions option D is incorrect.

I don’t get it why. Can’t we write (√ n) = O(n^2) ?

Or is it because we are asked for the tightest asymptotic bound? 

Please do let know!

Comments

It will be correct if “tight” keyword will not be there ?

---

haan bhai...

---

yes, i got it now. Thanks a lot!