Complexity of Programs 309It is most common to look only at the growth rate-up to O(*)--of the worst-case
complexity function. For example, choose as key operations comparisons of list elements,
swaps of list elements, or both. By any of these measures, BubbleSort is worst-case O(N^2 ),
and no matter how BubbleSort is improved, it still is worst-case O(N^2 ). Other sortingalgorithms are worst-case O(N • ln(N))-that is, algorithms that are, usually, much more
efficient. The discussion of decision trees in Section 6.12.4 of Chapter 6 deals with a lower
bound for a sorting algorithm of the same sort as BubbleSort. (We will clarify then what
"of the same sort" means.)Polynomial Time Algorithms
Any form of bubble sort algorithm, though intrinsically slow, can still be used for reason-
ably large data sets. A general question is to characterize what calculations are feasible. Of
course, that is really just a matter of how the word feasible is defined, but there is a signifi-
cant underlying intuition. Originally asked by theoreticians, the question also has practical
significance. For example, a basic goal of much modem research in cryptology, the study of
encrypting and decrypting messages, regards finding methods to encrypt messages where
breaking the code is, in principle, infeasible.Definition 1. An algorithm A is polynomial time if it is worst-case 0(nk) for some
integer k. That is, the function measuring its worst-case time complexity is less than or
equal to some polynomial function.
A decision problem is a problem whose answer is simply TRUE or FALSE.^1 The set
of all decision problems answered by polynomial-time algorithms is often referred to as P.
Sometimes, the notation P is also used to describe the set of polynomial-time algorithms.
The set of polynomial-time algorithms has been exceedingly important in studies of
computer algorithms. The interpretation given is that if an algorithm is polynomial time,
then it is conceivable that people might someday build a computer on which it can be run in
a reasonable amount of time for a relatively large input set. If an algorithm has a worst-case
time consumption greater than any polynomial, it is not.2Nondeterministic Polynomial Problems
The rest of this subsection develops material presented in Section 2.5.6, where we first
mentioned polynomial-time algorithms and the P : /'P conjecture. Readers who have
skipped that material may want to read that section.
Example 2. There is an O(n^2 ) algorithm such that:
Given: A propositional formula 4), such as,) = (a v b v c v d v -b) A (c v d v -c V e V f)
1 Many computer programs solve decision problems. Programmers write functions that return boolean values
to aid in similar programming circumstances. For example, while(NOT IsValidInput(InputData)) is true when
IsValidInput returns a value of FALSE. Sometimes, the purpose of an entire program is to compute a single
boolean result, such as "Can I buy this house with house payments of less than $1000 per month?" or "Did any
shop in my department have a below-average productivity during the month of December?" or "Can a salesman
visit all these cities and have to drive less than 1000 miles?"
2 If quantum computers become practically feasible, this view might change.