4 minutes,
2 points
1. In lecture you were told not to think of the
notation f(n) = O(g(n)) as an equality.
What are some better ways to refer to this notation? (Circle one)
a. “f(n) grows at most like
g(n)”
b. “f grows no faster than
g”
c. “f is bounded by g”
d. all of the above
2. Place the following complexity classes (with a problem size n) in
order from smallest to largest by labeling each class with a number from 1 - 6
(where 1 is the smallest complexity class and 6 is the largest).
_____ Exponential time: O(kn
)
_____ Constant time: O(k) or
O(1)
_____ Linear time: O(n)
_____ “n log n” time: O(n log n)
_____ Polynomial time: O(nk
)
_____ Logarithmic time:
O(log n)
3. (NOT REQUIRED) Prove/Show that the complexity function 7n3
+ 20n + 100 + 23n2 is O(n3). (Hint #1: argue that this function is O(n3)
by using the definition of what it means to say that
f(n) = O(g(n)) ).
(Bigger Hint #2: f(n)
= O(g(n)) is true if there is a constant c such
that f(n) = c * g(n) for all sufficiently large n.)
(Even Bigger Hint #3: Pick a
value for c and n that makes hint #2 true! Remember that the chosen value of c
is the more important of the two.)