Hint:

Notes: . All functions in this homework map RR+ The italics before a question provide motivation for the question for you to think about. You do not need to respond to the italicized prompt. Provide as tight a bound as possible on a range of functions. (20 points) Consider the set of functions G --,1, log n, logz n, Vn,_, logn , n, n log n, n2, n3,n1000,1.17,21,3n,n! For each of the following functions fi(n), find a function g1(n) E G and g2(n) E G, such that fi(n) - 2(g1 (n)) and fi(n) - 0(g2(n)) AND the bounds are as tight as possible. 2 fi(n) b. f2(n) -n2 3n2 -logn 101000 d. f4(n)= logn 3 7n Suppose that we have a function with a constant amount of work done in initialization, a call to a log-linear sorting algorithm, and a loop that iterates n times, doing a linear amount of work in each iteration. What is the running time of the algorithm? 4) For a given fi(n), g1(n) and g2(n) might be the same function, or they may be different