EE4371 Assignment2-Asymptotic analysis and Divide and Conquer Solved

Description

• Topics: Asymptotic analysis and Divide and Conquer

1. Order the following functions by asymptotic growth rate.

4n logn + 2n   2¹⁰      2^logn                           3n + 100logn  4n       2ⁿ                           n² + 10n          n³      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)

• n − 100 n − 200
• 100n + logn n + (logn)²
• log2n log 3n
• n⁰¹ nlog²n

 

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)
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).