Θ(lg n), Θ(n) and Θ(n2) are ____ in the amount of work they do as n increases.
A) restricted
B) useful
C) polynomially bounded
D) exponential

Question

Quizplus · Accepted Answer

The options describe the growth rates of algorithms. Theta notation specifies the upper and lower bounds of an algorithm's running time as n increases. 
- Theta of lg n represents an algorithm whose running time grows at most logarithmically as n increases. 
- Theta of n represents an algorithm whose running time grows linearly with n. 
- Theta of n^2 represents an algorithm whose running time grows quadratically with n. 
All three options describe polynomial growth, which is bounded by a power of n. Therefore, the answer is C, polynomially bounded.

Θ(Lg N), Θ(N) and Θ(N2) Are ____ in the Amount