1. Show the plotting commands and output for the Solved Exercise 1 on Page 65.

Take the following list of functions and arrange them in ascending order of growth rate. That is, if function g(n) immediately follows function f(n) in your list, then it should be the case that f(n) is O(g(n)). f1(n)=10nf2(n)=n1/3f3(n)=nnf4(n)=log2nf5(n)=2log2n Solution We can deal with functions f1,f2, and f4 very easily, since they belong to the basic families of exponentials, polynomials, and logarithms. In particular, by (2.8), we have f4(n)=O(f2(n)); and by (2.9), we have f2(n)=O(f1(n)). Now, the function f3 isn't so hard to deal with. It starts out smaller than 10n, but once n10, then clearly 10nnn. This is exactly what we need for the definition of O() notation: for all n10, we have 10ncnn, where in this case c=1, and so 10n=O(nn). Finally, we come to function f5, which is admittedly kind of strangelooking. A useful rule of thumb in such situations is to try taking logarithms to see whether this makes things clearer. In this case, log2f5(n)=log2n= (log2n)1/2. What do the logarithms of the other functions look like? logf4(n)= log2log2n, while logf2(n)=31log2n. All of these can be viewed as functions of log2n, and so using the notation z=log2n, we can write logf2(n)=31zlogf4(n)=log2zlogf5(n)=z1/2 Now it's easier to see what's going on. First, for z16, we have log2z z1/2. But the condition z16 is the same as n216=65,536; thus once n216 we have logf4(n)logf5(n), and so f4(n)f5(n). Thus we can write f4(n)=O(f5(n)). Similarly we have z1/231z once z9-in other words, once n29=512. For n above this bound we have logf5(n)logf2(n) and hence f5(n)f2(n), and so we can write f5(n)=O(f2(n)). Essentially, we have discovered that 2log2n is a function whose growth rate lies somewhere between that of logarithms and polynomials. Since we have sandwiched f5 between f4 and f2, this finishes the task of putting the functions in order