Question

Determine whether each of these functions is O(x^2 ).

(a) 100x + 1000

(b) 100x^(2) + 1000

(c) (x^(3)/100) ? 1000x^(2)

(d) x log x

Answer 1

it (a) 100x+1000

Explanation:

Answer 2

• (a) no
• (b) yes
• (c) no
• (d) no

Explanation:

"Of the order x^2" means the dominant behavior matches that of x^2 as x gets large. For polynomial functions, the dominant behavior is that of the highest-degree term.

For other functions, the dominant behavior will typically be governed in some other way. Here, the rate of growth of the x·log(x) function is determined by log(x), which has decreasing slope as x increases.

Only answer selection B has a highest-degree term of x^2, so only that one exhibits O(x^2) behavior.