Practical Programming, 2nd Edition

Sorting Out What You Learned

In this chapter, you learned the following:

• An invariant describes the data being used in a loop. The initial values for the variables used in the loop will establish the invariant, and the work done inside the loop will make progress toward the solution. When the loop terminates, the invariant is still true, but the solution will have been reached.

• Linear search is the simplest way to find a value in a list; but on average, the time required is directly proportional to the length of the list.

• Binary search is much faster—the average time is proportional to the logarithm of the list’s length—but it works only if the list is in sorted order.

• Similarly, the average running time of simple sorting algorithms ...