For each pair of functions f and g determine if f(n) ? O(g(n)), or f(n) ? ?(g(n)), or f(n) ? ?(g(n)).

In order to receive full credit, justify your answers. Example: f(n) = n 100 g(n) = n 200

In this case, we can see that both functions have the same linear growth. Thus, we know n 100 ? ?(n 200)

This could be shown with a limit and using LHopitals Rule: lim??? ? ?? ? 100 ?? ? 200 = lim??? ? 1 1 = 1

Since the result is a constant, this implies f(n) has the same order of growth as g(n). Thus: n 100 ? ?(n 200)

a. f(n) = n 2/3 g(n) = n 1/2

b. f(n) = log n + 100?n g(n) = (log n) 2 + n

c. f(n) = log 2n g(n) = log 3n

d. f(n) = n2 n g(n) = 3 n

e. f(n) = n! g(n) = 2 n