(10 pts) Rank the following functions by order of growth. That is, find an arrangement g1,g2,...,gn
of the functions satisfying g1 = O(g2), g2 = O(g3),
etc.
n log n, n3, 3n, n/(log n), sqrt(n), log(log n), log n, (log n)2,
(log n)sqrt(n), n2log n.
(10 pts) Problem 1.8 in text.
(10 pts) Problem 1.3 in text.
(10 pts) Fill in the table below with the worst-case time for each operation. Use big-O notation
and write your time bound in terms of n, the current number of items in the data
structure. The operations are insert (place a new item in the data
structure), getMin (return the value of the minimum item in the data structure
and delete
it), and reportMax (return the value of the maximum item in the data
structure without deleting it). Determine the best time bound that
you can without changing the data structure. Note that you can use O(1) extra space
if it helps achieve a better bound (if you use extra space, explain how you're using it).