 |
This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (March 2009) |
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.
For example, an algorithm which caches results for quick retrieval has the overhead of maintaining the cache memory. In terms of Algorithmic efficiency, overhead is often a term which is asymptotic but irrelevant.
Contents |
Example
There are two algorithms taking input of length n. Algorithm A takes n2 operations, and algorithm B takes 5n + 4 operations. For short inputs (n = 5 or less), algorithm A is more efficient. The + 4 in Algorithm B is the overhead: regardless of input, it takes 4 more operations than Algorithm A. It then takes 5 operations for each n. But Algorithm A takes n2 operations. If n > 5 then B is more efficient than A (for 6, n2 = 36 and 5n + 4 = 34). It is likely that n will more often than not be more than five, so B is generally more efficient, even with the overhead.
Choice of algorithm
A software engineer may have a choice of several algorithms, each of which have known characteristics. As seen above, some work well with small inputs, some with large; some with unsorted inputs, some with them mostly in order, and so on. Ideally, since the actual program code for the algorithms is usually very short, the engineer would have the computer choose each time the best one for the case. But of course the choice is itself an algorithm, and it could take the computer longer to choose than just going for what usually works best.
While naive engineers often try to reinvent the wheel, many algorithms are now standard, public, and well-documented for their efficiency and overhead characteristics.
Tradeoffs
In software engineering, overhead is a tool used to help decide 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.
Complexity
Algorithmic complexity is generally specified using Big O Notation. 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.
See also
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
