Let F(k) denote the kth Fibonacci number. The fastest known algorithm to compute F(2n), without using any non-integer values in our computation, takes ( ? ) time. a. n

b. None of the other choices

c. 2n

d. log

The Radio Interference problem: given the locations of n radio broadcasting centers and their broadcasting power, assuming they all use the same radio frequency channel, we want to determine whether there is any radio interference between them. More specifically, suppose we are given the xy-coordinates of each of these n centers in the plane, and we assume that their radio signals can propagate up to a given distance D in all directions in the plane. The problem is to determine whether there is any point in the plane that can receive a radio signal from more than one of these centers. This problem can be solved most efficiently in the worst case in ( ? ) time.

a. n

b. nlogn

c. 2^n

d. That's impossible to solve in finite time, since there are infinitely many candidate points in the plane to test.

e. n^2

The running time of the following pseudo-code fragment is ( ? ).

1 for 1 .. do 2 while < do +1 end-while end-for

a. nlogn

b. None of the other choices

c. nn

d. May not terminate for some n

e. nloglogn

f. n^2

The solution to the recurrence () = (/2) + (/3) + 8(/4) + 5(/6) + ^2 is () = ( ? ).

a. n^2

b. n^3

c. n^2logn

d. n^2loglogn

e. None of the other choices

f. n^2log^2n