CMSC 435 Algorithm Analysis & Design

Answers to Homework # 3

1. Text # 4

g₁(n) = 2^√log(n)

g₂(n) = 2ⁿ

g₃(n) = n(log n)³

g₄(n) = n^4/3

g₅(n) = n^log(n)

g₆(n) = 2^2**n

g₇(n) = 2^n**2

Take the log of each function:

log₂(g₁(n)) = √log(n)

log₂(g₂(n)) = n

log₂(g₄(n)) = (4/3) log(n)

log₂(g₅(n)) = log²n

log₂(g₆(n)) = 2ⁿ

log₂(g₇(n)) = n²

log₂(g₃(n)) = log(n) + 3log(log(n))

Then we have the order g₁, g_{3, g4}, g₅, g₂, g₇, g₆

2. Text # 5

Given f(n) = O(g(n))

a) log₂(f(n)) = O(log₂(g(n)) ? true use def. and take log of both sides except for the one case where f and g are both constant functions. f(n) = 2 and g(n) = 1

b) 2^f(n) = O(2^g(n))? false choose f(n) = 2n and g(n) = n

c) f(n)² = O(g(n)²) ? true, since f(n) <= cg(n) for all n: n>= n₀, we have (f(n)² <= c²(g(n))² for all n: n>= n₀

3. Text # 6

a) f(n) = O(n³). The line of code that adds the entries of the array from A[i] through A[j] executes at most n² times. Adding the array entries from A[i] through A[j] is O(j – i + 1) operations, which is always O(n). Storing the result in B[i, j] requires constant time. Therefore the runtime for the algorithm is at most n² O(n) = O(n³).

b) Consider the times when i <= n/4 and j >= 3n/4. In these cases j – i + 1 >= 3n/4 - n/4 + 1 > n/2. Therefore, adding up the array entries would require at least n/2 operations, since there are more than n/2 terms to add. How many times in the execution of the algorithm do we encounter such cases? There are (n/4)² pairs of (i, j) with i <= n/4 and j >= 3n/4 and the algorithm enumerates over all of them. Therefore the algorithm must perform at least (n/2)(n/4)² = n³/32 operations and hence is Ω(n³)

c) Consider the following algorithm

For i = 1, 2,…, n - 1

Set B[i, i+1] to A[i] + A[i+1]

For k = 2, 3,…, n-1

For i = 1, 2,…, n – k

Set j = i + k

Set B[i, j] = B[i, j – 1] + A[j]

4. Text # 7

Line 1 = <the Partridge family line goes here>

Line 2 = <second line of text>

…

Line L = <last line of text>

For i = 1, 2, …, L

<common line goes here>

For j = 1, 2, …, i

Sing lines j through 1

EndFor

EndFor

The nested for-loops have a length bounded by a constant c₁. Each of the lines in the script has length at most c₂ (where c₂ is the maximum line length c plus the space to write the variable assignment – the common line.) The total space required is therefore S = c₁ + c₂L. The value n denotes the number of words produced when sung and n >= ∑_k k = 1 + 2 + … + L = ½(L(L-1)). Hence n >= ½(L – 1)² So L <= 1 + √2n. Plugging this into the bound for the script we get f(n) = S <= c₁ + c₂√2n = O(√n)

5. Text # 8

a) Suppose for simplicity that n is a perfect square. We drop the first jar from heights that are multiples of √n until it breaks. If it survives a drop from the top rung, we are done, else if it breaks at a height of j√n, we start with a second jar at height (j – 1) √n and go up by 1 until it breaks. In this way we drop each of the two jars at most √n times. If the number of rungs is not a perfect square, we go up with the first jar in increments of |_√n_|. We get either way f₂(n) = O(√n).

b) By induction assume f_k(n) <= 2kn^1/k. Begin by dropping the first jar by multiples of |_n^(k-1)/k_|. |_n^(k-1)/k_| >= n^(k-1)/k/2, therefore we drop the first jar at most 2n/ n^(k-1)/k = 2n^1/k times. This narrows the set of rungs down to an interval of length at most n^(k-1)/k.

We then apply the strategy for k – 1 jars recursively. By induction, it uses at most 2(k – 1)( n^(k-1)/k)^1/(k-1) = 2(k-1)n^1/k drops. Adding in the <= 2n^1/k drops made using the first jar, we get a bound of 2kn^{1/k .} With k -1 jars left, the second drop will be in multiples of |_( n^(k-1)/k)^(k-2)(/k-1)_| and (let X = n^(k-1)/k) will be dropped at most 2X^1/(k-1) times. This forms an upper bound on how many times each of the succeeding jars will be dropped to get the 2(k –1)( n^(k-1)/k)^(k-1)/k drops.