What is the difference between time complexity and running time?

Question

What is the difference between time complexity and running time? Are they the same?

Czarra

It depends entirely on the context in which the term was used. When your boss is asking why the "run-time" was 3 hours, he isn't talking about algorithmic complexity. When your professor asks what the "run-time" of an algorithm is, he probably isn't asking you to get out your stopwatch and time it. – Scoles

Answer 1

Running time is how long it takes a program to run. Time complexity is a description of the asymptotic behavior of running time as input size tends to infinity.

You can say that the running time "is" O(n^2) or whatever, because that's the idiomatic way to describe complexity classes and big-O notation. In fact the running time is not a complexity class, it's either a duration, or a function which gives you the duration. "Being O(n^2)" is a mathematical property of that function, not a full characterisation of it. The exact running time might be 2036*n^2 + 17453*n + 18464 CPU cycles, or whatever. Not that you very often need to know it in that much detail, and anyway it might well depend on the actual input as well as the size of the input.

Community

"As the input size tends to infinity", true. – Staal

Is it OK to say that "the algorithm's runtime is O(n^2)" instead of saying "the algorithm's running time is O(n^2)" (i.e. "runtime" instead of "running time" for short)? – Unearthly

@AlwaysLearning: sure, I'd understand that. – Community

Answer 2

The time complexity and running time are two different things altogether.

Time complexity is a complete theoretical concept related to algorithms, while running time is the time a code would take to run, not at all theoretical.

Two algorithms may have the same time complexity, say O(n^2), but one may take twice as much running time as the other one.

Warman

Agreed. However when we have two different approaches for same problem, is it wise to compare the running time for different approaches to make sure we are calculating time complexity correctly? -- From a beginner perspective? – Lacedaemon

Answer 3

From CLRS 2.2 pg. 25

The running time of an algorithm on a particular input is the number of primitive operations or “steps” executed. It is convenient to define the notion of step so that it is as machine-independent as possible.

Now from Wikipedia

... time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.

Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation takes a fixed amount of time to perform.

Notice that both descriptions emphasize the relationship of the size of the input to the number of primitive/elementary operations.

I believe this makes it clear both refer to the same concept.

In practice though you'll find that enterprisey jargon rarely matches academic terminology, e.g., tons of people work doing code optimization but rarely solve optimization problems.

Ingravescent

Answer 4

"Running time" refers to the algorithm under consideration:

Another algorithm might be able solve the same problem asymptotically faster, that is, with less running time.

"Time complexity" on the other hand is inherent to the problem under consideration. It is defined as the least running time of any algorithm solving said problem.

The same distincting applies to other measures of algorithmic cost such as memory, #processors, communication volume etc.

(Blum's Speedup Theorem demonstrates that the "least" time may in general not be attainable...)

Surrounding

Answer 5

To analyze an algorithm is to determine the amount of resources (such as time and storage) necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length. Usually the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps (time complexity) or storage locations (space complexity).

Tawnatawney

Answer 6

Running time measures the number of operations it takes to complete a code or program. the keyword here is "operations" and "complete", the time taken for every single operation to complete can be affected by the processor, memory, etc.

With running time, If we have 2 different algorithms solving the same problem, the optimized algorithm might take a longer time to complete than the non-optimized one because of varying factors like ram, the current state of the PC (serving other programs) etc. or even the function for calculating the runtime itself.

For this reason, it is not enough to measure the efficiency of an algorithm based on operations it takes to complete but rather time against input, that way all the external factors are eliminated and that's exactly what time complexity does.

Time complexity is the measurement of an algorithm's time behavior as input size increases.

Time complexity can also be calculated from the logic behind the algorithm/code. On the other hand, running time can be calculated when the code is completed.

Billiton

Answer 7

Time Complexity is the measure of number of operations in the algorithm, so this is fixed for a particular algorithm

Running Time is the real clock time the machine takes to execute those operations in the algorithm, this depends on many factors like machine's configuration, current load in that machine and many more and thus it is not fixed for a particular algorithm

Margiemargin

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Howardhowarth