Cost Models
Time efficiency estimates depend on what we define to be a step. For the analysis to correspond usefully to the actual execution time, the time required to perform a step must be guaranteed to be bounded above by a constant. One must be careful here; for instance, some analyses count an addition of two numbers as one step. This assumption may not be warranted in certain contexts. For example, if the numbers involved in a computation may be arbitrarily large, the time required by a single addition can no longer be assumed to be constant.
Two cost models are generally used:
- the uniform cost model, also called uniform-cost measurement (and similar variations), assigns a constant cost to every machine operation, regardless of the size of the numbers involved
- the logarithmic cost model, also called logarithmic-cost measurement (and variations thereof), assigns a cost to every machine operation proportional to the number of bits involved
The latter is more cumbersome to use, so it's only employed when necessary, for example in the analysis of arbitrary-precision arithmetic algorithms, like those used in cryptography.
A key point which is often overlooked is that published lower bounds for problems are often given for a model of computation that is more restricted than the set of operations that you could use in practice and therefore there are algorithms that are faster than what would naively be thought possible.
Read more about this topic: Analysis Of Algorithms
Famous quotes containing the words cost and/or models:
“This people must cease to hold slaves, and to make war on Mexico, though it cost them their existence as a people.”
—Henry David Thoreau (1817–1862)
“Friends broaden our horizons. They serve as new models with whom we can identify. They allow us to be ourselves—and accept us that way. They enhance our self-esteem because they think we’re okay, because we matter to them. And because they matter to us—for various reasons, at various levels of intensity—they enrich the quality of our emotional life.”
—Judith Viorst (20th century)