Question

Prove that f(x) = x^3 – 1000x^2 + x – 1 is ω(x^3) and o(x^3).

Answer 1

F(x) = x 3 − 1000x^2 + x − 1

> x3 − 1000x^ 2

= (x − 1000)x^2

> (.9x)x^2

= .9x^3

Therefore, f(x) is Ω(x^3 ) with C = .9, k = 10, 000. Also, for all x > 0:
 
f(x) = x^3 − 1000x^2 + x − 1

< x^3 + 1000x^3 + x^3 + x^3

= 1002x^3

Therefore, f(x) is O(x^3 ) with C = 1002, k = 1.