Given the tight asymptotic bound for the recurrence equation :
T(n) = 2T($\frac{n }4{}$) + 1
- O(√ n)
- Ω(√ n)
- θ(√ n)
- 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!