Description
- 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)
- Write a recurrence for T(n). (You may assume arithmetic operations take time in Θ(1).)
- 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)
- 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).
- 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.
- Tabulate T(n), for n from 1 to 10, with s = u = 0.6, and also with s = 0.6 and u = 0.
- 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.
- 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.
