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

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

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.