algorithm

Question

Which is not O(n^2)?

a) (15^10) *n +12099

b) n^1.98

c) n^3 / sqrt(n)

d) (2^20)*n

Comments

only c) is not O(n²)....

n³/sqrt(n)= n^2.5= O(n³)

---

even option a and d is not O(n^2)

they are O(n) right?

---

but O(n) can be bounded in O(n²), since n²>n,

and yes a) and d) has a tightest upper bound as O(n), but they can be also bounded in O(n²)

---

got it :)