Answers are in bold blue
To within a constant factor, what is the fastest that a comparison algorithm can sort a list of n values?
THETA(n lg(n))
To within a constant factor, what is the solution to the following recurrence? Assume that T(n) is bounded by a constant for small values of n.
T(n) = 9T(n/3) + n
T(n) = THETA(n2). Use the master theorem, with a = 9, b = 3, f(n) = n. Then logb(a) = 2, and n2 is the dominant term.
Let f(n) = n3lg(n) and g(n) = n4. Is f(n) O(g(n))? Is g(n) O(f(n))? Justify your answer.
The ratio n3 lg(n) / n4 is lg(n)/n. Since lg(n) grows slower than n, the limit of that ration is 0. So f(n) is O(g(n)), but g(n) is not O(f(n)).
A particular divide-and-conquer algorithm, when run on an input of size n, works by spending O(n) time splitting the problem in half, then does a recursive call on each half, then spends O(n2) time combining the solutions to the recursive calls. On small inputs, the algorithm takes a constant amount of time. To within a constant factor, how long does this algorithm take, in terms of n?
The recurrence is T(n) = 2T(n/2) + O(n) + O(n2). But that has the same asymptotic solution as recurrence T(n) = 2T(n/2) + n2, since n2 dominates n. The master theorem gives solution T(n) = O(n2).
You are given a list x1, ..., xn of n different positive numbers, in no particular order, and a positive integer k < n. You need to find k values a1, ..., ak from the input list, where a1 < a2 < ... < ak, with the following property.
For convenience define a0 = 0 and ak+1 = infinity. Let set sj be {xi | aj <= xi < aj+1}, for j = 0, ..., k. That is, sj consists of all members of the input list that lie between aj and aj+1. The desired property is that all of the sets s0, ..., sk have approximately the same size. (Their sizes should differ by at most 1.)
(If k = 2, then the idea is to select values that divide the list into thirds, by cutting it at two places. If k = 99, the list is being divided into 100 equal sections by the selected values.)
Use the fast selection algorithm k times to find the cut points. Each selection takes O(n) time, so the total time for k selections is O(kn).
Sort the list. Then the cut points are found by their position in the sorted list. Sorting takes time proportional to n lg(n).
The switchover occurs when kn > n lg(n). That is, k > lg(n).
The fast divide-and-conquer integer multiplication algorithm gets its speed from a clever trick that allows it to do only three recursive calls instead of four. Does the trick mean that it takes only 3/4 as long as our first divide-and-conquer algorithm (which does four recursive calls), or is it not that much better, or does it take even less than 3/4 as much time?
The fast algorithm gets a factor of 3/4 speed-up at each level of the recursion tree. The more recursive calls you do them more speedup you get. It does much better then merely 3/4 as much time. It uses so much less time that, as n grows larger and larger, the ratio of the time required by the fast algorithm to the time required by the slower algorithm approaches 0.
A complex number is represented by a pair of real numbers. (The pair (a,b) is usually written (a + bi), but we will just write a complex number as a pair of real numbers here.) The product of two complex numbers (a,b) and (c,d) is defined to be the complex number (ac-bd, ad+bc). Clearly, the product of two complex numbers can be computed by doing four multiplications of real numbers. Show how to compute the product of two complex numbers using only three multiplications of real numbers. You can do any constant number of additions and subtractions, but you must assume that real numbers are stored to arbitrary precision, and the number of additions and subtractions that you do must not depend on the precision of the numbers.
Compute
p1 = ac
p2 = bd
p3 = (a+b)(c+d)
x = p1 - p2
y = p3 - p1 - p2
Then the answer is (x,y). Notice that only 3 multiplications are done.