NPTEL-Design and Analysis of Algorithms-Week1-Quiz-1-Q6

Question

if T(n) = n² √ n then

1. T(n) = O(n²)
2. T(n) = O(n² log n)
3. T(n) = O(n³)
4. None of the above

Im getting option 2 is it correct ?

Comments

No, because $n^2logn = O(n^2 \sqrt{n})$

See How function behaves for large value of $n$. (say $n = 10^{1000})

---

just for sake of answer, it should be O(n^3)

---

1. n² √ n  = omega (n²)
2. n² √ n =   omega  (n² log n)
3. n² √ n  = O(n³)

***********   √ n is asymptotically greater than log n *******