In computational complexity, an algorithm is said to take linear time, or O(n) time, if the time it requires is proportional to the size of the input, which is usually denoted n. Put another way, the running time increases linearly with the size of the input. For example, a procedure that adds up the elements of a list requires time proportional to the length of the list.
This description is slightly inaccurate, since the running time can significantly deviate from a precise proportionality, especially for small n. Technically, it's only necessary that for large enough n, the algorithm takes more than an time and less than bn time for some positive real constants a,b. For more information, see the article on Big O notation.
Linear time is often viewed as a desirable attribute for an algorithm. Much research has been invested into creating algorithms exhibiting (nearly) linear time or better. This research includes both software and hardware methods. In the case of hardware, some algorithms which, mathematically speaking, can never achieve linear time with the standard computation model are now able to run in linear time. There are several hardware technologies which exploit parallelism to provide this. An example is associate memory.
For a given sorting algorithm, it can be proven that there exists an order of number which this sorting algorithm will execute in linear time. However, for a general case, no sorting algorithm can perform better than n*lg(n) where lg is log of base 2.
Lineartime is a major feature of our Western cultural world-view, apparently initiated by Newton some 300 years ago.
But lineartime, which is an experiential perspective completely independent of clock time, combines (1) the actual feeling of time slipping from one moment to another, and (2) many different feelings--like overwhelm, pressure, anxiety, hurry, time poverty, frustration, and boredom--that we have as and about time.
With the experience of time flowing between past, present, and future there is a dissatisfied self 'spending time' in the foreground.
Spacetime is four-dimensional and a continuum, with time being a distinguished, one-dimensional sub-space of this continuum.
These features don't require time to be linear rather than circular because a segment of a circle is also a linear continuum, but there is no evidence for circular time, that is, for causal loops or closed timelike curves.
Proper time along a worldline in 4-d spacetime is the time elapsed by an object having that worldline, as shown on an ideal clock having the same worldline.
Feeds |
Contact