Are the following true? Justify your answers. (a) If f ( n ) = a 0 + a 1 n + + aknk and g ( n ) = b 0 + b 1 n + bk + mnk + m, where ai , b j are any real numbers ak , bk + m > 0 , k ≥ 0 , and m ≥ 1 ,...

Are the following true? Justify your answers.

(a) If
f
(n) =
a0 +
a1n
+ +
aknk
and
g(n) =
b0 +
b1n
+
bk+mnk+m,
where
ai , b j
are any real numbers
ak , bk+m >
0, k
≥ 0,
and
m
≥ 1,
then
f
(n) =
O(g(n)) but
g(n) _
O(
f
(n)).

(b) If
m, k
≥ 1, then (log
n)k
=
O(nm) but
nm
_
O((log
n)k
).

(c)
nO(1) is the set of all functions that are bounded above by some polynomial.

(d)
f
(n)O(1) is the set of all functions that are polynomial in
f
(n).
Functions in (log
n)O(1) are called
polylogarithmic bounded functions.