Time Complexity

What Does Time Complexity Mean?

Time complexity is a concept in computer science that deals with the quantification of the amount of time taken by a set of code or algorithm to process or run as a function of the amount of input.

Advertisements

In other words, time complexity is essentially efficiency, or how long a program function takes to process a given input.

Techopedia Explains Time Complexity

Time complexity is simply a measure of the time it takes for a function or expression to complete its task, as well as the name of the process to measure that time. It can be applied to almost any algorithm or function but is more useful for recursive functions. There is little point in measuring time complexity for applications such as fetching the username and password from a database for comparison or simply saving data whether it is 20 ms or 5 ms; that would be more in the line of access time. It has nothing to do with caring about its execution time, but rather that the difference is negligible. However, if there is a recursive function that may be called multiple times, determining and understanding the source of its time complexity may help shorten the overall processing time from, say, 600 ms to 100 ms.

Time complexity is expressed typically in the "big O notation," but there are other notations. This is a mathematical representation of the upper limit of the scaling factor for an algorithm and is written as O(Nn), with "N" being the number of inputs and "n" being the number of looping expressions. For example, we have the algorithm:




 numbers[] = {5,6,10,11,2};

foreach (number as number1)

{

 foreach(number as number2)

{

 statements;

 }

 }

There are five inputs in the "numbers" array, and the "foreach" loop is repeated twice. Therefore, exponential growth in processing time occurs as the number of inputs and the number of loops grow.

Advertisements

Related Terms

Latest Computer Science Terms

Related Reading

Margaret Rouse

Margaret Rouse is an award-winning technical writer and teacher known for her ability to explain complex technical subjects to a non-technical, business audience. Over the past twenty years her explanations have appeared on TechTarget websites and she's been cited as an authority in articles by the New York Times, Time Magazine, USA Today, ZDNet, PC Magazine and Discovery Magazine.Margaret's idea of a fun day is helping IT and business professionals learn to speak each other’s highly specialized languages. If you have a suggestion for a new definition or how to improve a technical explanation, please email Margaret or contact her…