3
$\begingroup$

Is time complexity and running time of the program/algorithm one and the same thing? Also, running time sounds like 'computer complexity'. As, it utilizes all the resources and give tangible time that program took to run. So, can we say that running time is same as computer complexity?

$\endgroup$
5
$\begingroup$

The terms, as they are used in computational complexity theory are different.

Running time is a property of an algorithm. It is the maximum number of steps the algorithm can run for, as a function of the length of the input.

Time complexity is a property of a computational problem. It is, essentially, the running time of the fastest possible algorithm for that problem.

Thus, we might talk about the time complexity of the sorting problem, and the running time of heapsort. Informally, people often refer to the "time complexity" of an algorithm. Strictly speaking, this is incorrect, but there's only really one thing it could mean.

Note that we usually only quote the asymptotic behaviour of running times and time complexities, since we're usually not interested in the exact function, and it's usually too hard to figure out, anyway.

Note also that, in applied computing, "running time" may refer to the time taken for some program to run, as you might measure with a stopwatch.

$\endgroup$
  • $\begingroup$ Thanks for the clarification Mr. Richerby. So if I understand correctly, would it be correct to think the difference between running time and time complexity is where the focus lies? To elaborate, what I understood is that running time is focused on particular algorithm instances and their input, whereas time complexity seems to focus more on the general problem at hand. $\endgroup$ – Seankala Jun 6 '18 at 19:21
  • $\begingroup$ Yeah, that’s the gist of it. $\endgroup$ – David Richerby Jun 6 '18 at 20:03
-1
$\begingroup$

They're both essentially trying to describe the same thing (performance) but in different ways.

Running time is how long it takes for a computer to perform a specific task. This could be measured in nanoseconds, milliseconds, etc.

In contrast, time complexity is a more abstract and general way of expressing performance, and is a generalized and more abstract representation of run time. To be specific, it's a representation of the asymptotic behavior of the run time as the run time approaches infinity. I'm not sure if you're familiar with notations such as big O notation, but it looks something like this:

$$O(1)\\O(n)\\O(\log{n})$$

and the list goes on. The Wikipedia article I linked has a good list of the notations regarding time complexity.

When I first ran into time complexity, it was difficult for me to grasp (aside from personal factors like I had no background knowledge in computer science) because I just didn't know what expressions like "asymptotic behavior" meant and I couldn't wrap my head around the formal definitions either (obviously).

When I asked my professor about it, he told me to think of it more as growth rates. The lower the growth rate, the better (this statement is terribly generalized, but let me explain).

Let's say you have two functions, $y = x^2$ and $y = x$. If you graph them, they look like this:

enter image description here

As you can see, $y = x^2$ "grows" at a much faster rate than $y = x$. But in terms of complexity, lower growth rates are better because it means the time it takes for the program to run is that much closer to being linear, and that's why in terms of time complexity $O(n)$ is better than $O(n^2)$.

I hope my answer helps. Good luck!

EDIT

To answer your edited question, no; run time and computational complexity are not the same thing.

Computational complexity, as you mentioned, talks about the resources that a computing device needs to perform a task. Therefore, run time is a factor of computational complexity and so they aren't equal.

$\endgroup$
  • $\begingroup$ This is not how the terms are used in complexity theory. $\endgroup$ – David Richerby Jun 6 '18 at 18:30
-1
$\begingroup$

No. The difference is well explained by Steve Jessop: "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."

Soure: https://stackoverflow.com/questions/4915842/difference-between-time-complexity-and-running-time

EDIT: Here is the video that might be helpful for your edited question: https://www.youtube.com/watch?v=8syQKTdgdzc

$\endgroup$
  • $\begingroup$ This is not how the terms are used in computational complexity. $\endgroup$ – David Richerby Jun 6 '18 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.