Big O notation is an effective way to measure how quickly things grow. In class we discuss the definition, that big O notation is an equivalence relation of functions from R+ to R+ defined by O(f) = O(g) if

limx→∞ f(x)/g(X) = C ∈ R+

We say that f is polynomial complexity if there exists an n ∈ N with O(f) ≤ O(xn), and we say that it is exponential complexity if there exist real numbers a,b both greater than 1 with O(ax) ≤ O(f) ≤ O(bx). Give an example of a function g with O(g) > O(f) for every polynomial complexity function but O(g) < O(f) for every exponential complexity function.