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. The time 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).
Explain why any comparison algorithm that finds the second smallest of n values can be extended to find both the smallest and the second smallest values without performing even one more comparison. That is, if you have put in the effort to find only the second smallest, then you have no choice but to have obtained enough information to know the smallest as well.
Any comparison algorithm to find the second smallest value must, at some point, have compared the second smallest value to the smallest. If it didn't, then it doesn't have enough information to know which of the smallest and the second smallest is actually the second smallest. So the algorithm knows exactly one value that is smaller than the second smallest. That one is the smallest. No additional comparisons are needed.
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.