Computational overhead
From Wikipedia, the free encyclopedia
Jump to: navigation, search
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.