Constant time

Constant time

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 does not depend on the size of the data it is given as input.

For example, accessing any single element in an array or memory bank 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.

ee also

*Big O notation
*Exponential time
*Linear time
*Polynomial time


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Time complexity — In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O… …   Wikipedia

  • time perception — Introduction       experience or awareness of the passage of time.       The human experience of change is complex. One primary element clearly is that of a succession of events, but distinguishable events are separated by more or less lengthy… …   Universalium

  • time interval — noun a definite length of time marked off by two instants • Syn: ↑interval • Hypernyms: ↑measure, ↑quantity, ↑amount • Hyponyms: ↑access time, ↑distance, ↑ …   Useful english dictionary

  • Constant folding — and constant propagation are related compiler optimizations used by many modern compilers. An advanced form of constant propagation known as sparse conditional constant propagation can more accurately propagate constants and simultaneously remove …   Wikipedia

  • Constant Change — Studio album by Jose Mari Chan Released December 31, 1989 …   Wikipedia

  • Constant Shallowness Leads to Evil — Studio album by Coil Released 2000 Septemb …   Wikipedia

  • Constant voltage speaker system — Constant voltage speaker systems refer to networks of loudspeakers which are connected to an audio amplifier using step up and step down transformers to simplify impedance calculations and to minimize power loss over the speaker cables. They are… …   Wikipedia

  • Constant rate factor — (CRF) is a x264 s single pass encoding method. Contents 1 Overview 2 Technical details 3 Not a common knowledge 4 See also …   Wikipedia

  • Constant — Con stant, n. 1. That which is not subject to change; that which is invariable. [1913 Webster] 2. (Math.) A quantity that does not change its value; used in countradistinction to {variable}. [1913 Webster] 3. (Astron.) A number whose value, when… …   The Collaborative International Dictionary of English

  • Constant of aberration — Constant Con stant, n. 1. That which is not subject to change; that which is invariable. [1913 Webster] 2. (Math.) A quantity that does not change its value; used in countradistinction to {variable}. [1913 Webster] 3. (Astron.) A number whose… …   The Collaborative International Dictionary of English

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”