For instance, if there are eight items in the
list, the algorithm will complete in (3 + 1) iterations or fewer.
In any case, the running time of the binary search is ??(lg n). This efficiency recommends it as a search
algorithm, and also, therefore, often justifies the work of keeping frequently searched lists in order.
Intractable problems
The algorithms discussed so far all have an order of growth that can be described by some polynomial equation
in n. A ???polynomial in n??? means the sum of some number of terms, where each term consists of n raised to some
power and multiplied by a coefficient. For instance, the insertion sort order of growth is (n2/2 - n/2).
When an algorithm has an order of growth that is greater than can be expressed by some polynomial equation
in n, then computer scientists refer to the algorithm as intractable. If no better algorithm can be discovered to
solve the problem, computer scientists refer to the problem as an intractable problem.
As an example of an intractable problem, consider a bioinformatics problem. The Department of Genetics at
Yale School of Medicine maintains a database of genetic information obtained from different human populations.
ALFRED (ALlele FREquency Database) is a repository of genetic data on 494 anthropologically defined
human populations, for over 1600 polymorphisms (differences in DNA sequences between individuals).
Pages:
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70