Description
1. (18p). Assuming that A[1..n] is non-decreasing and that x occurs in A[1..n], consider the below program
(which may be what you constructed in Assignment 1):
lo, hi, q ← 1, n,(1 + n) div 2
while A[q] 6= x
if A[q] < x
lo ← q + 1
else
hi ← q − 1
q ← (lo + hi) div 2
return q
If n = 1, the body of the while loop will not be executed; if n = 2, it will be executed once (if A[1] < x) or
not at all (if A[1] = x); if n = 3, it will be executed once (if A[2] 6= x) or not at all.
Let U(m) denote the maximum number of iterations of the while loop body when A[lo..hi] has m elements
(that is, m = hi − lo + 1). We can thus tabulate the first entries of U as follows:
m 1 2 3 4 5 6 7 8 9
U(m) 0 1 1
1. (5p): Find U(4). You must argue for your answers.
2. (5p): Provide the remaining missing entries in the above table, that is, compute U(m) for m = 5..9.
You do not need to argue for your answers.
3. (4p): Use your table to write a recurrence (a recursive equation) that (for m ≥ 2) expresses U(m) in
terms of U(b
m
2
c). You do not need to argue for your answer, but show that for m = 3, 8 it coincides
with your answer to (2).
4. (4p): Find a general formula (not recursively defined) for U(m). You do not need to argue for your
answer, but show that for m = 1, 3, 8 it coincides with your answer to (2).
2. (12p). For each of the following functions f of n, indicate how big the natural number n must be in
order for f(n) to be at least 10,000, and for f(n) to be at least 100,000,000 (that is, 108
). You may give
approximate answers but they should have at least two significant figures.
n n lg(n) n
√3 n n
√
n n
2 n
4
(1.001)n (1.1)n 2
n 100n n! n
n
3. (10p). Prove, using only the definition of “big-O” and not any auxiliary results stated on the slides or
in the textbook(s), that
1. (5p): 3n
4 + 7n
3 + 6n
2 + 9n + 5 ∈ O(n
4
)
2. (5p): n
5 − 7n
4 + 2n
2 − n /∈ O(n
4
)
