1. Order the following functions by asymptotic growth rate.
4n logn + 2n 210 2logn 3n + 100logn 4n 2n n2 + 10n n3 nlogn
2. In each of the following situations, indicate whether f = O (g),or f = Ω (g),or both (in which case f = Θ(g)). Justify your answer.
f (n) g (n)
(a) n − 100 n − 200
(b) 100n + logn n + (logn)2
(c) log2n log 3n
(d) n1.01 nlog2n
3. Describe an efficient algorithm for finding the ten largest elements in a sequence of size n . What is the running time of your algorithm?
4. Use the divide and conquer integer multiplication algorithm to multiply the two binary integers 10011011 and 10111010.
5. You are given a unimodal array of n distinct elements, meaning that its entries are in increasing order up until its maximum elements, after which its elements are in decreasing order. Give an algorithm to compute the maximum element of a unimodal array that runs in O(log n) time.
6. You are given an array of n elements, and you notice that some of the elements are duplicates; that is, they appear more than once in array. Show how to remove all duplicates from the array in time O(n log n).
