[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Any problem that has only finitely many possible inputs can be solved in O(1) time on a standard RandomAccessMachine by including a very large table of all possible inputs and the corresponding output for each. An example of such an algorithm in real life is the usual implementation of isspace, isalpha, and similar macros in the standard C library. In practice, you should probably use table lookup only if the table is small, frequently used, and computing individual values at run-time takes long enough the precomputation pays off.


2014-06-17 11:58