Write all problem solutions neatly by hand. You can also type out the solutions. Include the plots and justification for R3.1.

Submit a pdf file including all your work. Also submit the py file for problem 3.1.

type

----------------------------------------------------------------------------------------------------------------------------------------------------

R3.1 ---> Use the matplotlib to generate the plots. The file runningtimetest.py uses matlplotlib along with plot and scatter funtions to generate plots. Submit your py file. Also put the plots in a pdf file and submit with the rest of your homework. Comment on the order of growth of each funtion that you plotted. Sort the functions in the order that they grow.

R-3.8 Order the following functions by asymptotic growth rate. 4nlog n+2n 210 2log n 3n+100log n 4n 2n n2 +10n n3 nlogn

R-3.17 Show that (n+1)5 is

O(n5). R-3.18 Show that 2n+1 is O(2n)

R-3.19 Show that n is O(nlogn). R-3.20 Show that n2 is (nlogn). R-3.21 Show that nlog n is (n).

R-3.29 Algorithm A executes an O(log n)-time computation for each entry of an n-element sequence. What is its worst-case running time?

R-3.30 Given an n-element sequence S, Algorithm B chooses logn elements in S at random and executes an O(n)-time calculation for each. What is the worst-case running time of Algorithm B?

R-3.33 Al and Bob are arguing about their algorithms. Al claims his O(nlogn)- time method is always faster than Bobs O(n2)-time method. To settle the issue, they perform a set of experiments. To Als dismay, they find that if n < 100, the O(n2)-time algorithm runs faster, and only when n 100 is the O(nlogn)-time one better. Explain how this is possible.