Computational overhead
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 attain a particular goal. It is a special case of engineering overhead
.
, overhead can influence the decision whether or not to include features in new products, or indeed whether to fix bugs. A feature that has a high overhead may not be included – or needs a big financial incentive to do so. Often, even though software providers are well aware of bugs in their products, the payoff
of fixing them is not worth the reward, because of the overhead.
. This makes no comment on how long something takes to run or how much memory it uses, but how its increase depends on the size of the input. Overhead is deliberately not part of this calculation, since it varies from one machine to another, whereas the fundamental running time of an algorithm does not.
This should be contrasted with efficiency, which takes into account all kinds of resources – a combination (though not a trivial one) of complexity and overhead.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, overhead is generally considered any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to attain a particular goal. It is a special case of engineering overhead
Engineering overhead
In engineering, some methods or components make special demands on the system. The extra design features necessary to accommodate these demands are called overhead. Expenses not directly related to the production and sale of a product. For example, income...
.
Communications
- Sending a payload of data (reliably) over a communications network requires sending more than just the desired payload data, itself. It also involves sending various control and signalling data (TCPTransmission Control ProtocolThe Transmission Control Protocol is one of the core protocols of the Internet Protocol Suite. TCP is one of the two original components of the suite, complementing the Internet Protocol , and therefore the entire suite is commonly referred to as TCP/IP...
) required to achieve the reliable transmission of the desired data in question. The control signalling is overhead.- A simplified version is the need and time to dial a number to establish a phone call, before the call can take place. Dialing the number and establishing the call are overhead.
- Another simplified scenario is in the use of 2-way (but half-duplex) radios. Overhead would be the use of “over” and other signalling needed to avoid collisions, as extra traffic to that of the actual message(s) to be conveyed.
Vehicles & travel
- Travel using a vehicle involves the overhead of transporting the vehicle (plus payload) to the destination, rather than just the payload. Energy must be used to move the mass of the vehicle, in addition to the passengers and/or cargo.
- Time to complete a journey always includes a fixed amount of time needed to make preparations in order to actually begin travelling. Imagine boarding a shared vehicle (a train, or aircraft), or dressing warmly to leave the building and get into a car. This fixed ‘setup’ time is overhead to the journey itself.
Choice of algorithm
A programmer/software engineer may have a choice of several algorithms, each of which have known characteristics. When choosing among them, their respective overhead should also be considered.Tradeoffs
In software engineeringSoftware engineering
Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
, overhead can influence the decision whether or not to include features in new products, or indeed whether to fix bugs. A feature that has a high overhead may not be included – or needs a big financial incentive to do so. Often, even though software providers are well aware of bugs in their products, the payoff
Payoff
Payoff may refer to:* Bribery* A payoff dominant equilibrium in game theory* Payoff matrix or payoff function in a normal form game in game theory* Payoff set in set theory* Payoff, a 1991 TV film starring Keith Carradine...
of fixing them is not worth the reward, because of the overhead.
Complexity
Algorithmic complexity is generally specified using Big O NotationBig O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
. This makes no comment on how long something takes to run or how much memory it uses, but how its increase depends on the size of the input. Overhead is deliberately not part of this calculation, since it varies from one machine to another, whereas the fundamental running time of an algorithm does not.
This should be contrasted with efficiency, which takes into account all kinds of resources – a combination (though not a trivial one) of complexity and overhead.