- an
is any well-defined computational procedure that takes some value, or set of values, as*algorithm*and produces some value, or set of values, as*input*. An algorithm is thus a sequence of computational steps that transform the input into the output.*output* - An input sequence is called an
of the sorting problem*instance* -
Which algorithm is best for a given application depends on-among other factors

**the number of items to be sorted****the extent to which the items are already somewhat sorted****possible restrictions on the item values****The kind of storage device to be used**

- An algorithm is said to be
if, for every input instance, it halts with the correct output*correct* -
Why are NP-complete problems interesting?

- First, although no efficient algorithm for an NP-Complete problem has ever been found, nobody has ever proven that an efficient algorithm for one cannot exist.
- Second, the set of NP-Complete problems has the remarkable property that if an efficient algorithm exists for any one of them, then efficient algorithms exists for all of them. This relationship among the NP-Complete problems makes the lack of efficient solutions all the more tantalizing

Third, several NP-Complete problems are similar, but not identical, to problems for which we do know of efficient algorithms. A small change to the problem statement can cause a big change to the efficiency of the best known algorithm.

Advertisements