inputs → algorithms → outputs

As we try to process inputs to produce outputs, we need to come up with algorithms that are not only correct, but also efficient, such that we can get answers quickly to problems with large input sizes.

Suppose you could have either

Though a million dollars might sound good, you should pick the latter option whenever asked to make such decision in life. Since the amount of money you get is doubled each day, the total amount of money you get will outgrow one million dollars before the end of the month, as illustrated by this Excel table.

Suppose you had to detect if a sorted array A had duplicates. In other words, given a sorted array A, find indices i and j where A[i] = A[j]. The array might look something like this:

One approach could be to create a list of pairs and iterate through all pairs until you find a pair with the same numbers: (-3, -1), (-3, 2), (-3, 4), …​, (10, 12). But your instinct should tell you that this is not the most efficient solution. If $N$ is the size of the array, this algorithm would generate $\frac{N^2}{2} - \frac{N}{2}$ pairs. And then you’d have to go through those pairs and look for one with the same numbers. This algorithm would take roughly $N^2$ steps.

A much better algorithm would be to compare each number A[i] with A[i + 1]. We can do this since the array is sorted! This algorithm would take at most $N - 1$ steps.