1. Consider the following program (which may be what you constructed in Assignment 1) whose running time T(n) we want to estimate, as a function of n = hi − lo:
Find(x,A,lo,hi)
q ← (lo + hi) div 2 if A[q] = x return q
else if A[q] < x return Find(x,A,q + 1,hi) else return Find(x,A,lo,q − 1)
1. Write a recurrence for T(n). (You may assume arithmetic operations take time in Θ(1).)
2. Solve that recurrence, by using the “Master Theorem”. (You should indicate which version you use, and what are the given values of a, b, etc)
2. Solve each of the recurrences
(1)
(2)
(3)
Your answers should be of the form T(n) ∈ Θ(f(n)), with f as simple as possible. You should justify your answers, for example by appealing to the “Master Theorem” (if applicable).
3. Given real numbers s,u with 0 < s ≤ u ≤ 0.8, consider the function T given by
T(n) = 2n for n ≤ 4
T(n) = T(dsne) + T(dune) + 1 for n ≥ 5
This is well-defined, since when n ≥ 5 then n − un = (1 − u)n ≥ 0.2n ≥ 1 and thus dsne≤dune < n.
1. Tabulate T(n), for n from 1 to 10, with s = u = 0.6, and also with s = 0.6 and u = 0.8.
2. Use the substitution method to find a constraint on the values of s and u such that you can prove by induction in n that
T(n) ≥ cn2 for all n ≥ 0
for some positive real number c; list the largest c that will work.
3. Compare your “experimental” results from part 1 to your “theoretical” results from part 2. That is, for s = u = 0.6 and also for s = 0.6,u = 0.8, tell whether the constraint from part 2 is satisfied; if so, with c the constant you found in part 2, tell whether T(n) ≥ cn2 does indeed hold for all n ≤ 10.
