For each of the following pairs of equations determine wheth

For each of the following pairs of equations, determine whether the f(n ) is O(g(n)), (g(n)), or (g(n)). Show all work.

1. f(n) = 5 / lg n, g(n) = lg n

Solution

The answer is f(n) = O(g(n))

If the base of logarithm is b, then for some m > b, lg m > 1. So for n>b

lg n > 1/(lg n) So for c = 5 and m = b

f(n) = O(g(n))