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 expanded 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 n2 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.
