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:
“I favor the policy of economy, not because I wish to save money, but because I wish to save people. The men and women of this country who toil are the ones who bear the cost of the Government. Every dollar that we carelessly waste means that their life will be so much the more meager. Every dollar that we prudently save means that their life will be so much the more abundant. Economy is idealism in its most practical terms.”
—Calvin Coolidge (1872–1933)
“The parents who wish to lead a quiet life I would say: Tell your children that they are very naughty—much naughtier than most children; point to the young people of some acquaintances as models of perfection, and impress your own children with a deep sense of their own inferiority. You carry so many more guns than they do that they cannot fight you. This is called moral influence and it will enable you to bounce them as much as you please.”
—Samuel Butler (1835–1902)