Question 1 (4 marks)
Using L’Hˆopital’s Rule, prove that for all k > 0:
1. (3 marks) n
k ∈ ω(ln n).
2. (3 marks) n
k ∈ o(e
n
).
Question 2 (18 marks)
Consider the following algorithm.
sum = 0;
for (i=1; i<=n; i++)
for (j=1; j<=i*i; j++)
if (j%i==0)
for (k=1; k<=j; k++)
sum++;
1. (4 marks) Implement the above algorithm and plot the problem size n versus T(n) for
n = 1..20. Use sum as a proxy for T(n).
2. (10 marks) Derive an exact expression for T(n) and empirically show that T(n) equals
sum for n = 1..20.
Hint: Rewrite the algorithm without the if condition.
3. (4 marks) State and prove the exact order time complexity T(n).
Question 3 (13 marks)
1. (6 marks) Using the Master Theorem, find the exact order time complexity of:
T(n) = 3 T(2n/3) + n
3
Ensure that all conditions are met.
2. (3 marks) Show why the Master Theorem presented in class cannot solve the exact
order time complexity of:
T(n) = 2 T(n/2) + n lg n.
3. (4 marks) Determine the largest integer value for a such that S(n) = a S(n/4) + n
2
is
asymptotically faster than T(n) = 5 T(n/2) + n