Constant time
From Wikipedia, the free encyclopedia
In computational complexity theory, constant time, or O(1) time, refers to the computation time of a problem when the time needed to solve that problem is bounded by a value that does not depend on the size of the data it is given as input.
For example, accessing any single element in an array takes constant time as only one operation has to be made to locate it. However, finding the minimal value in an unordered array is not a constant time operation as a scan over each element in the array is needed in order to determine the minimal value. Hence it is a linear time operation, taking O(n) time (unless some more efficient algorithm is devised, for example, a binary search across a sorted array). 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 time does not have to be strictly independent of the problem size, but only has to be bounded independently of the problem size. For example, the task "exchange the values of a and b if necessary so that a≤b" is called constant time even though the time may depend on whether or not it is already true that a≤b. The important thing is that there is some constant t such that the time required is always at most t.
Here are some examples of code fragments that run in constant time:
int index = 5; int item = list[index];
if (condition true) then perform some operation that runs in constant time else perform some other operation that runs in constant time
for i = 1 to 100 perform some operation that runs in constant time
for i = 1 to 100
for j = 1 to 200
perform some operation that runs in constant time
Note that O(1) is a standard notation to denote constant time. For this reason, it is not normal practice to write, say O(100), even if the algorithm runs 100 times.
[edit] See also
 |
This computer science article is a stub. You can help Wikipedia by expanding it. |
