CIS575-Assignment 2 Solved

Description

1. 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:

1. : Find U(4). You must argue for your answers.
2. Provide the remaining missing entries in the above table, that is, compute U(m) for m = 5.. You do not need to argue for your answers.
3. 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. 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. 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, 10⁸). You may give approximate answers but they should have at least two significant figures.

n  nlg(n)      n√³ n     n√n                n² n⁴ (1.001)ⁿ  (1.1)ⁿ 2ⁿ 100ⁿ n!                nⁿ

3. Prove, using only the definition of “big-O” and not any auxiliary results stated on the slides or in the textbook(s), that
   1. 3n⁴ + 7n³ + 6n² + 9n + 5 ∈ O(n⁴)
   2. n⁵− 7n⁴ + 2n²− n /∈ O(n⁴)