Description
● Topics: Asymptotic analysis and Divide and Conquer
1. Order the following functions by asymptotic growth rate.
4n logn + 2n 2
10 2
logn
3n + 100logn 4n 2
n
n 0n
2 + 1 n
3 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) n nlog n
1.01 2
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).
