In Exercises 1–14, to establish a big-O
relationship, find witnesses
C
and
k
such that |f (x)| ≤
C|g(x)| whenever
x > k.
1. Determine whether each of these functions is
O(x).
a)
f (x)
= 10 b)
f (x)
= 3x
+ 7
c)
f (x)
=
x
2+
x
+ 1 d)
f (x)
= 5 log
x
2. Determine whether each of these functions is
O(x2).
a)
f (x)
= 17x
+ 11 b)
f (x)
=
x2 + 1000
c)
f (x)
=
x
log
x
d)
f (x)
=
x4/2
3. Use the definition of “f (x)
is
O(g(x))” to show that
x
4+ 9x
3+ 4x
+ 7 is
O(x
4
).
4. Use the definition of “f (x)
is
O(g(x))” to show that 2
x
+ 17 is
O(3
x
).
5. Show that
(x
2+ 1)/(x
+ 1)
is
O(x).
6. Show that
(x
3+ 2x)/(2x
+ 1)
is
O(x
2
).
7. Find the least integer
n
such that
f (x)
is
O(xn)
for each of these functions.
a)
f (x)
= 2x
3+
x
2
log
x
b)
f (x)
= 3x
3+
(log
x)
4
c)
f (x)
=
(x
4+
x
2+ 1)/(x
3+ 1)
d)
f (x)
=
(x
4+ 5 log
x)/(x
4+ 1)
8. Find the least integer
n
such that
f (x)
is
O(xn)
for each of these functions.
a)
f (x)
= 2x
2+
x
3
log
x
b)
f (x)
= 3x
5+
(log
x)
4
c)
f (x)
=
(x
4+
x
2+ 1)/(x
4+ 1)
d)
f (x)
=
(x
3+ 5 log
x)/(x
4+ 1)
9. Show that
x
2+ 4x
+ 17 is
O(x
3
)
but that
x
3
is not
O(x
2+ 4x
+ 17).
10. Show that
x
3
is
O(x
4
)
but that
x
4
is not
O(x
3
).
11. Show that 3x
4+ 1 is
O(x
4
/2)
and
x
4
/2 is
O(3x
4+ 1).
12. Show that
x
log
x
is
O(x
2
)
but that
x
2
is not
O(x
log
x).
13. Show that 2
n
is
O(3
n)
but that 3
n
is not
O(2
n).
14. Determine whether
x
3
is
O(g(x))
for each of these functions
g(x).
a)
g(x)
=
x
2
b)
g(x)
=
x
3
c)
g(x)
=
x
2+
x
3
d)
g(x)
=
x
2+
x
4
e)
g(x)
= 3
x
f )
g(x)
=
x
3
/2