# Algorithms and Complexity by Herbert S. Wilf By Herbert S. Wilf

Best combinatorics books

Handbook of Algebra Vol III

1998 . .. an exceptional index is incorporated on the way to support a mathematician operating in a space except his personal to discover enough info at the subject in query.

Additional info for Algorithms and Complexity

Example text

We would like to rearrange these numbers as necessary so that they end up in nondecreasing order of size. This operation is called sorting the numbers. For instance, if we are given {9, 4, 7, 2, 1}, then we want our program to output the sorted array {1, 2, 4, 7, 9}. There are many methods of sorting, but we are going to concentrate on methods that rely on only two kinds of basic operations, called comparisons and interchanges. This means that our sorting routine is allowed to: (a) pick up two numbers (‘keys’) from the array, compare them, and decide which is larger.

N in the inner loop. This means that the total number of comparisons is: f1 (n) = n−1 X n X n−1 X (n − r) 1 r=1 j=r+1 = r=1 = (n − 1)n/2. Thus, the number of comparisons is Θ(n2 ), which is quite a lot of comparisons for a sorting method to do. , its best case and its worst case are equally bad. The Quicksort1 method, which is the main object of study in this section, does a maximum of cn2 comparisons, but on the average it does far fewer, a mere O(n log n) comparisons. This economy is much appreciated by those who sort, because sorting applications can be immense and time consuming.

Consider the recurrence: xn+1 = 2xn − xn−1 (n ≥ 1; x0 = 1; x1 = 5). 39) If we try a solution of the type xn = αn , then we find that α satisfies the quadratic equation α2 = 2α − 1. Hence, the ‘two’ roots are 1 and 1. The general solution is xn = 1n (c1 + nc2 ) = c1 + c2 n. 39) is given by xn = 4n + 1. Now let’s look at recurrent inequalities, like this one: xn+1 ≤ xn + xn−1 + n2 (n ≥ 1; x0 = 0; x1 = 0). 40)? 32 1. Mathematical Preliminaries By analogy with the case of diﬀerence equations with constant coefficients, the thing to try here is xn ≤ Kαn .