Assignment 2

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

1

EE 4371

# Assignment 2: Asymptotic analysis and Divide and Conquer

Original price was: $35.00.$30.00Current price is: $30.00.

## Reviews

There are no reviews yet.