September 5th, 2016

In Technology

No Comments

If you enjoy this article, see the other most popular articles

If you enjoy this article, see the other most popular articles

If you enjoy this article, see the other most popular articles

# Accessing any single element in an array takes constant time as only one operation has to be performed to locate it.

(written by lawrence krubner, however indented passages are often quotes). You can contact lawrence at: lawrence@krubner.com, or follow me on Twitter.

This seems like it could be used as a trick question that would trip me up during a job interview:

An algorithm is said to be constant time (also written as O(1) time) if the value of T(n) is bounded by a value that does not depend on the size of the input. For example, accessing any single element in an array takes constant time as only one operation has to be performed 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. 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 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. However, 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 for j = 1 to 200 perform some operation that runs in constant timeIf T(n) is O(any constant value), this is equivalent to and stated in standard notation as T(n) being O(1).

### Post external references

- 1

https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time

September 2, 2021 7:47 pm

From Mojavedfo on Where PHP regex fails

"55 thousand Greek, 30 thousand Armenian..."