Computational overhead

From Wikipedia, the free encyclopedia

In computer science, overhead is generally considered any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to be utilized or expended to enable a particular goal. It is a special case of engineering overhead.

For example, an algorithm which caches frequent results for quick retrieval has the overhead of maintaining the memory to store the cached results. In terms of Algorithmic efficiency, overhead is often the terms which are asymptotically irrelevant. Consider two algorithms based on input length n: algorithm A, which takes n² operations, and algorithm B, which takes 4n + 7 operations. On short inputs such as n = 2, algorithm A is more efficient. Algorithm B is said to have overhead which constitutes the 4 extra operations for each input length and 7 additional operations (overhead may be used to describe all or any part of the additional operations). However, when the input is large, say n = 1000, algorithm B is much more efficient. Overhead may also be used to decide whether or not to include features in software engineering. If developing for an embedded system, a feature that has a high memory overhead may not be included.