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 CS575
(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 CS575
