Problem 1:Let n be a positive integer. Partition the following set of 15 functions into equivalence classes

such that f(n) and g(n) are in the same equivalence class if and only if f(n) = ?(g(n)). (If a base of a

logarithm is not specified, it is assumed to be equal 2.)

9 log 3

? n

n n 8e 2 +

1

e n

4 log 8 + 2 n log(4 n )

nlog(n!) 4 (

n

2 )

n 2 4 n + n 5 (0.5) n

n! n n + n! 2 2n n 2 logn log 5 (n

1

3 )

Then arrange the equivalence classes into a sequence

C 1 ,C 2 ,C 3 ···

such that for any f(n) ? C i and g(n) ? C i+1 f(n) = O(g(n)).

Problem 2: An elevator brought you to the ground floor of a building. You want to exit the building.

You don’t know, where the exit from the building is. There are 5 different paths that you can take. The

problem is that all five paths are infinitely long, and only one of them has a door that you can use to exit

the building. The distance between the elevator and the door is no less than 30 steps. (Make sure to use

this information!) You don’t know, which of the four paths has the door, but you will see it once you are in

front of it. Design an algorithm that enables you to find the door by walking at most O(n) steps, where n

is the number of steps that you would have taken if you knew where the door is and walked directly to it.

What is the constant multiple in the big-O bound for your algorithm?

Problem 3: Use the method of iterative substitution to solve the following recurrence. Give the asymptotic

solution as well. Assume that T(n) is constant for n ? 5.

1

Homework 1: CS 141

(Asymptotic notations)

Intermediate Data Structures and Algorithms

T(n) =

(

c if n ? 5

T(n ? 4) + log(n) if n > 5

Problem 4:

(a) Use the method of iterative substitution to solve the following recurrence.

T(n) =

(

2 if n ? 7

T(n 1/3 ) + ?(loglogn) if n > 7

(b) Use mathematical induction to prove that your asymptotic solution for (a) is correct.

Problem 5: Euclid’s algorithm uses the following simple formula, which leads to the algorithm below.

Euclid’s rule If x and y are positive integers with x ? y, then gcd(x,y) = gcd(x mod y,y).

procedure Euclid(a, b)

input: a,b are integers with a ? b ? 0

output: gcd(a,b)

if b = 0 : return a

return Euclid(b,a mod b)

Here, we will look at an alternative algorithm based on divide and conquer.

(a) Show that the following rule is true.

gcd(a,b) =

?

?

?

?

?

2gcd(a/2,b/2) if a,b are even

gcd(a,b/2) if a is odd, b is even

gcd((a ? b)/2,b) if a,b are odd

(b) Give an efficient divide-and-conquer algorithm for greatest common divisor. (You can write it in plain

English or use pseuodocode.) Argue the correctness and running time of your algorithm.