Consider the following pair of recurrences: An = 7An1 + 2Bn2 for n2, and A0=A1=1 Bn = 4Bn1 + 5An2 for n2, and B0=B1=2 . For any given n, the most efficient method to compute the exact value of An takes ( ? ) time.

a. n

b. n^2

c. 2^n

d. logn

e. These two recurrences depend on each other and the problem does not have a solution.

Fill in the underlined blank for the following algorithm.

algorithm exp (,) // Pre-Condition: is a positive real number and is a natural number // Post-Condition: returns ^ begin 1 while ( >0 ) do // Loop Invariant: _____________________________ // fill in this line if ( ( mod 2)=1) then /2 end-while return end

If there is more than one correct choice, then select the blue choice.

a. more than one of the other choices are correct

b. the desired output value equals the current value of r x^y

c. r will eventually become the desired output value

d. the loop repeatedly multiplies r by ( mod 2), doubles x, and halves y

Suppose f(n) = (n^4log^2n) and g(n) = (n^3logn). Then

a. f(n)/g(n) = O(nlogn)

b. f(n)/g(n) = (nlogn)

c. f(n)/g(n) = (nlogn)

d. f(n)g(n) = (^7log^3)

The solution to the recurrence T(n)=4T(n)+(log^2n)(loglogn) is T(n)= ( ? ).

a. nlognloglogn

b.log^3(n^3logn)

c. log^2(nlogn)

d. (lognloglogn)^2