Description
1. (10p). 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. (5p) Write a recurrence for T(n). (You may assume arithmetic operations take time in Θ(1).)
2. (5p) 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. (12p). Solve each of the recurrences
T(n) = 3 T(
n
3
) + n
2
(1)
T(n) = 9 T(
n
3
) + n
2
(2)
T(n) = T(n − 1) + n
√
n (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. (18p). 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. (5p) 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. (8p) 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. (5p) 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.
