## Description

1. [30%] Prove the following using the original definitions of O, Ω,Θ, o,

and ω.

(a) 10n

3 + 2n + 15 = O(n

3

).

(b) 7n

2 = Ω(n).

(c) 5n

2 = ω(n).

(d) 7n

3 + 15n

2 + 5 = Θ(n

3

).

(e) p(n) = Pk

i=1 ain

i = Θ(n

k

) where ai > 0.

2. [20%] Prove the following using limits.

(a) n

k = o(3n

) where k > 0.

(b) n= ω(lg n

5

).

3. [10%] Prove that 3

n − 1 is divisible by 2 for n = 1, 2, 3, … by induction. Divide your proof into the three required parts: Induction Base,

Induction Hypothesis, and Induction Steps.

4. [10%] Prove or disprove that n

3 = O(n

2

).

5. [10%] Just say True or False for the following.

(a) 1000000n

2 + 5000 = Θ(n

2

).

1

(b) 2

n+1 = O(2n

).

(c) n

3 + n

2 + 100n = Ω(n

3

).

(d) n

1000 = ω(2n

).

(e) logn100 = Ω(logn).

6. [10%] Analyze the worst case time complexity of recursive binary search

using the iterative method. Assume the number of data n = 2k

.

7. [10%] The following pseudo code computes a factorial for input parameter n that is expressed via s bits where n, s ≥ 1. What is the time

complexity of the pseudo code?

unsigned int fact(unsigned int n) {

unsigned int p = 1;

for (i=1; i≤ n; i++) p = p * i;

return p;

}

2