Content deleted Content added
m Removed category "Computer science"; Quick-adding category "Computational complexity theory" (using HotCat) |
→Definitions of variables: wikilink |
||
Line 3:
== Definitions of variables ==
Metrics are usually described in terms of variables that are a function of the input. For example, the statement that [[insertion sort]] requires [[Big-O notation|O]](''n''<sup>2</sup>) comparisons is meaningless without defining ''n'', which in this case is the number of elements in the input list.
Because many different contexts use the same letters for their variables, confusion can arise. For example, the complexity of [[primality test]]s and [[multiplication algorithm]]s can be measured in two different ways: one in terms of the integers being tested or multiplied, and one in terms of the number of [[binary numeral system|binary]] digits (bits) in those integers. For example, if ''n'' is the integer being tested for primality, [[trial division]] can test it in Θ(n<sup>1/2</sup>) arithmetic operations; but if ''n'' is the number of bits in the integer being tested for primality, it requires Θ(2<sup>n/2</sup>) time. In the fields of [[cryptography]] and [[computational number theory]], it is more typical to define the variable as the number of bits in the input integers.
| |||