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:
“Life! Life! Don’t let us go to life for our fulfilment or our experience. It is a thing narrowed by circumstances, incoherent in its utterance, and without that fine correspondence of form and spirit which is the only thing that can satisfy the artistic and critical temperament. It makes us pay too high a price for its wares, and we purchase the meanest of its secrets at a cost that is monstrous and infinite.”
—Oscar Wilde (1854–1900)
“Grandparents can be role models about areas that may not be significant to young children directly but that can teach them about patience and courage when we are ill, or handicapped by problems of aging. Our attitudes toward retirement, marriage, recreation, even our feelings about death and dying may make much more of an impression than we realize.”
—Eda Le Shan (20th century)