In algorithmic analysis , one is interested in the amount of resources used by an algorithm and in the algorithm's correctness. The time complexity measures the amount of time used. The space complexity measures the amount of space used. The best case, average case and worst case complexities are of interest.
Logic is invaluable in program proof .
The mathematics required for this analysis is summarised here. A mathematically able reader should skip this chapter. Other readers should scan it quickly and refer back to it when the material is needed in later sections. Recurrence Relations Recurrence relations often arise in calculating the time and space complexity of algorithms. The solutions of recurrence relations are often best proved by induction as illustrated in some of the following sections.