3 Logarithmic functions grow more slowly than "polynomial" functions The textbook (2.8, page 41) provides the following useful fact, stating roughly that logarithmic functions are big-O-upper-bounded by simple "polynomial" functions, specifically functions that are n to some constant power: Fact: For every b > 1 and every x > 0, we have logb n = O(n x ). 1. (4 points) Use the fact above to prove the stronger assertion that logarithmic functions of n grow strictly more slowly, in the little-o sense, than functions that are n to some constant power: For every b > 1 and every x > 0, we have logb n = o(n x ). If you want, you can start your proof as follows: Fix b > 0 and x > 0. Using the fact, and since x/2 > 0, it must be the case that logb n = O(n x/2 ). 2. (4 points) Now use the fact of part 1 to show that n = o(n/ log3 n). Here the log is to the base 10, and log3 n = (log n) 3