T(n) = 9T(n/4) + O(n)
Use the master theorem with a = 9, b = 4 and f(n) = n. Then logb(a) is about 1.58, and the solution is THETA(nlog4(9)).
f(n)/g(n) = n/(log2(n))2. But n grows much
faster than (log2(n))2. (Remember that
any fixed power of log(n) grows slower than any fixed positive power
of n.) So the limit as n goes to infinity of f(n)/g(n) is infinity.
g(n) is O(f(n)), but f(n) is not O(g(n)).
The recurrence is T(n) = 3T(n/3) + O(n). The master theorem tells us that the solution is T(n) = THETA(n log(n)).
Describe an algorithm that solves this problem in time O(n), independent of the value of k.
The values sought are those that are less than or equal to the k-th smallest value in the list. Use the fast selection algorithm to find the k-th smallest value (call it V), then examine each of the values in the original list, printing those that are less than or equal to V.
To within a constant factor, how large should k be before method (b) is faster than method (a)?
Method (a) takes time O(nk), since it calls for k linear searches,
each having cost O(n).
Method (b) takes time O(n log(n) + k log(n)), since sorting
takes time O(n log(n)), and then the k binary searches cost
O(k log(n)) time (O(log(n)) time each).
The two functions cross where they are equal. So set
nk = n log(n) + k log(n). Solving this yields
k = (n log(n)) / (n - log(n))
k(n - log(n)) = n log(n)
Notice that log(n) is very small compared to n, so n - log(n) is
approximately n. Since we are only getting the crossover value
k to within a constant factor anyway (having ignored the big-O),
k = log(n)
will do. For k larger than log(n), solution (b) is preferred.