Editing Time complexity (section)

== Constant time ==
{{redirect|Constant time|programming technique to avoid a timing attack|Timing attack#Avoidance}}

An algorithm is said to be '''constant time''' (also written as <math display="inline">O(1)</math> time) if the value of <math display="inline">T(n)</math> (the complexity of the algorithm)  is bounded by a value that does not depend on the size of the input. For example, accessing any single element in an [[array data structure|array]] takes constant time as only one [[Instruction (computer science)|operation]] has to be performed to locate it. In a similar manner, finding the minimal value in an array sorted in ascending order; it is the first element. However, finding the minimal value in an unordered array is not a constant time operation as scanning over each [[element (math)|element]] in the array is needed in order to determine the minimal value. Hence it is a linear time operation, taking <math display="inline">O(n)</math> time. If the number of elements is known in advance and does not change, however, such an algorithm can still be said to run in constant time.

Despite the name "constant time", the running time does not have to be independent of the problem size, but an upper bound for the running time has to be independent of the problem size. For example, the task "exchange the values of {{mvar|a}} and {{mvar|b}} if necessary so that <math display="inline">a \le b</math>" is called constant time even though the time may depend on whether or not it is already true that <math display="inline">a \le b</math>. However, there is some constant {{mvar|t}} such that the time required is always ''at most'' {{mvar|t}}.