An algorithm is said to take linear time, or O(n) time, if its time complexity is O(n). Informally, this means that for large enough input sizes the running time increases linearly with the size of the input. For example, a procedure that adds up all 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 values of n.
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 standard computation models are able to run in linear time. There are several hardware technologies which exploit parallelism to provide this. An example is content-addressable memory. This concept of linear time is used in string matching algorithms such as the Boyer-Moore Algorithm and Ukkonen's Algorithm.
Read more about this topic: Time Complexity
Famous quotes containing the word time:
“Anybody who knows the difference between the kind of conversation you have walking in the woods and the kind of conversation you have between the segments of a show on Nickelodeon can tell you that quality time exists. Quality time is when you and your child are together and keenly aware of each other. You are enjoying the same thing at the same time, even if it is just being in a room or going for a drive in the car. You are somehow in tune, even while daring to be silent together.”
—Louise Lague (20th century)