Editing Analysis of algorithms (section)

== Cost models ==
Time efficiency estimates depend on what we define to be a step. For the analysis to correspond usefully to the actual run-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:<ref name="AhoHopcroft1974">{{cite book|author1=Alfred V. Aho|author2=John E. Hopcroft|author3=Jeffrey D. Ullman|title=The design and analysis of computer algorithms|url=https://archive.org/details/designanalysisof00ahoarich|url-access=registration|year=1974|publisher=Addison-Wesley Pub. Co.|isbn=9780201000290}}, section 1.3</ref><ref name="Hromkovič2004">{{cite book|author=Juraj Hromkovič|title=Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography|url=https://books.google.com/books?id=KpNet-n262QC&pg=PA177|year=2004|publisher=Springer|isbn=978-3-540-14015-3|pages=177–178}}</ref><ref name="Ausiello1999">{{cite book|author=Giorgio Ausiello|title=Complexity and approximation: combinatorial optimization problems and their approximability properties|url=https://books.google.com/books?id=Yxxw90d9AuMC&pg=PA3|year=1999|publisher=Springer|isbn=978-3-540-65431-5|pages=3–8}}</ref><ref name=Wegener20>{{Citation|last1=Wegener|first1=Ingo|title=Complexity theory: exploring the limits of efficient algorithms|publisher=[[Springer-Verlag]]|location=Berlin, New York|isbn=978-3-540-21045-0|year=2005|page=20|url=https://books.google.com/books?id=u7DZSDSUYlQC&pg=PA20}}</ref><ref name="Tarjan1983">{{cite book|author=Robert Endre Tarjan|author-link=Robert Endre Tarjan|title=Data structures and network algorithms|url=https://books.google.com/books?id=JiC7mIqg-X4C&pg=PA3|year=1983|publisher=SIAM|isbn=978-0-89871-187-5|pages=3–7}}</ref>
* the '''uniform cost model''', also called '''unit-cost model''' (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 similar variations), assigns a cost to every machine operation proportional to the number of bits involved

The latter is more cumbersome to use, so it is 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.<ref>[https://cstheory.stackexchange.com/q/608 Examples of the price of abstraction?], cstheory.stackexchange.com</ref>