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)...


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

Nov 11, 2021
SOLUTION.PDF

Get Answer To This Question

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here