- an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.
- An input sequence is called an instance of the sorting problem
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 correct if, for every input instance, it halts with the correct output
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.