Source code online books for professionals by professionals

pSeUDOpOLYNOMIaLItY
nice word, huh? It’s the name for certain algorithms with exponential running time that “look like” they have 
polynomial running times and that may even act like it in practice. The issue is that we can describe the running 
time as a function of many things, but we reserve the label “polynomial” for algorithms whose running time is 
a polynomial in the size of the input—the amount of storage required for a given instance, in some reasonable 
encoding. Let’s consider the problem of primality checking or answering the question “Is this number a prime?” 
This problem has a polynomial solution, but it’s not entirely obvious ... and the entirely obvious way to attack it 
actually yields a nonpolynomial solution.

---

ChapTer 3 
■
 CounTIng 101
51
here’s my stab at a relatively direct solution:
 
def is_prime(n):
    for i in range(2,n):
        if n % i == 0: return False
    return True
 
The algorithm here is to step through all positive integers smaller than n, starting at 2, checking whether they 
divide n. If one of them does, n is not a prime; otherwise, it is. This might seem like a polynomial algorithm, and 
indeed its running time is 
Q(n). The problem is that n is not a legitimate problem size!
It can certainly be useful to describe the running time as linear in n, and we could even say that it is polynomial 
... in n. But that does not give us the right to say that it is polynomial ... period. The size of a problem instance 
consisting of n is not n, but rather the number of bits needed to encode n, which, if n is a power of 2, is roughly  
lg n + 1. For an arbitrary positive integer, it’s actually 
floor(log(n,2))+1
.
Let’s call this problem size (the number of bits) k. We then have roughly n = 2
k–1
. our precious 
Q(n) running time, 
when rewritten as a function of the actual problem size, becomes 
Q(2
k
), which is clearly exponential.
5
 There are 
other algorithms like this, whose running times are polynomial only when interpreted as a function of a numeric 
value in the input. (one example is a solution to the knapsack problem, discussed in Chapter 8.) These are all 
called pseudopolynomial.
The relation to subsets is quite direct: If each bit represents the presence or absence of an object from a size-k set, 
each bit string represents one of the 2
k
 possible subsets. Perhaps the most important consequence of this is that any 
algorithm that needs to check every subset of the input objects necessarily has an exponential running time complexity.
Although subsets are essential to know about for an algorist, permutations and combinations are perhaps a bit 
more marginal. You will probably run into them, though (and it wouldn’t be Counting 101 without them), so here is a 
quick rundown of how to count them.
Permutations are orderings. If n people queue up for movie tickets, how many possible lines can we get? Each 
of these would be a permutation of the queuers. As mentioned in Chapter 2, the number of permutations of n items 
is the factorial of n, or n! (that includes the exclamation mark and is read “n factorial”). You can compute n! by 
multiplying n (the number of possible people in the first position) by n–1 (remaining options for the second position) 
and n–2 (third ...), and so forth, down to 1:
n
n n
n
!
(
) (
)
= × - × - × × ×
1
2
2 1

Not many algorithms have running times involving n! (although we’ll revisit this count when discussing limits to 
sorting, in Chapter 6). One silly example with an expected running time of Q(n · n!) is the sorting algorithm bogosort, 
which consists of repeatedly shuffling the input sequence into a random order and checking whether the result is sorted.