Question

2. Select a theta notation from Table 4.3.3 for each expression

2n^2 + 1
6n^3 + 2n^2 + 1
50n^2 + 5n + 1
2n + 1
2n - 1

Answer 1

TABLE 4.3.3 ■ Common
growth functions.
Theta Form Name
(1) Constant
(lg lg n) Log log
(lg n) Log
(n) Linear
(n lg n) n log n
(n2) Quadratic
(n3) Cubic
(nk), k ≥ 1 Polynomial
(cn), c > 1 Exponential
(n!) Factorial