Chapter 10 Flashcards
What is sieve technique
Sieve technique is a special case of divide-and-conquer. divide-and-conquer is breaking the problem into a small number of smaller sub-problems, which are then solved recursively. The sieve technique is a special case, where the number of sub-problems is just 1. The sieve technique works in phases. It applies to problems where we are interested in finding a single item from a larger set of n items. We do not know which item is of interest, however after doing some amount of analysis of the data, taking say Q (n k) time, for some constant k, we find that we do not know what the desired the item is, but we can identify a large enough number of elements that cannot be the desired value, and can be eliminated from further consideration. Then we apply recursion. Each of the resulting recursive solutions then do the same thing, eliminating a constant fraction of the remaining set.
