Related Topics
- Recurrences
Functions frequently used in the formal analysis of recursive algorithms. Recurrences are represented as recursive functions. A recursive function is a function that calls itself (see Chapter 3). Each successive call works on a more refined set of inputs, bringing us closer and closer to a solution. They are useful in describing the performance of recursive algorithms because they allow us to describe an algorithm’s performance in terms of invoking the algorithm on a more and more refined set of inputs.
- Summation formulas
Mathematical formulas useful in simplifying summations that describe the running times of algorithms. Summations occur frequently as the result of analyzing iterative control structures.
- Θ-notation, Ω-notation, o-notation, and w-notation
Additional notations used to represent information about an algorithm’s performance. Whereas O -notation expresses the upper bound of a function within a constant factor, Θ -notation expresses a bound from above and below. Ω -notation expresses strictly a lower bound within a constant factor. o -notation and w -notation are analogous to O -notation and Ω-notation but are more precise. O -notation often is used informally where other notations would be more specific.
- NP-complete problems
A class of problems for which no polynomial-time algorithms are known, but for which no proof exists refuting the possibility either. Thus, NP-completeness has long been one of the most perplexing vexations in computer ...