Description

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 ). 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).
n nlg(n) n√3 n n√n n2 n4 (1.001)n (1.1)n 2n 100n n! nn
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): 3n4 + 7n3 + 6n2 + 9n + 5 ∈ O(n4)
2. (5p): n5− 7n4 + 2n2− n /∈ O(n4)