4
$\begingroup$

Is there a difference between the computational complexity and computational cost of an algorithm?

$\endgroup$
  • 2
    $\begingroup$ This is too broad and opinion-based question, though interesting one. $\endgroup$ – fade2black Nov 4 '17 at 19:32
7
$\begingroup$

To answer your question as stated: "computational complexity" typically refers to the $\Theta$-class of a certain (often implicit) measure of computational cost.

That said, I prefer to use the terms like this:

  • Use "complexity" when talking about problems. For instance, you can say "sorting has $\Theta(n \log n)$ worst-case time complexity (in the comparison model)".

  • Use "costs" when talking about algorithms. You would say, "Mergesort has a worst-case running-time cost in $\Theta(n \log n)$ (under the RAM model)".

This is consistent with common use, that is every expert will understand what you're saying, but avoids using the term "complexity" for different things.

Rationale

  1. Complexity theory and analysis of algorithms (AofA) are distinct fields with different goals and techniques. It's not helpful to use terminology that muddles the two together.

    Side note: teaching only the complexity-theory side of things makes large parts of the AofA literature inaccessible to computer science graduate, which I think is a shame. See the work of Flajolet and Sedgewick if you're interested in these things.

  2. "Cost", other than "complexity", is used for precise measures like, say, "the number of comparisons" often analysed in sorting. Such a cost measure is (given an algorithm and a machine model) a well-defined function on the inputs (other than "time") and can be analysed rigorously.

  3. Every algorithm has many cost measures with different asymptotic behavious; in sorting, for instance, number of comparisons, swaps, and many more. Therefore, asking for "the complexity of the algorithm" is an oversimplification, and only meaningful under certain assumptions/conventions.

  4. The analysis of cost measures can yield testable hypotheses, if it's more precise than Landau bounds. "Complexity" results are not testable.

  5. "Complexity" of an algorithm can be rigorously defined in terms of cost measures, if one so desires. The other way around does not work.

    For instance, an algorithm's "(time) complexity" is usually taken to mean the $\Theta$-class of dominant, additive cost measure that is defined by a function on basic operations. However, I consider this practice confusing and thus harmful (cf. item 1), and prefer to say "[cost measure] is in $\Theta(\_)$".

$\endgroup$
  • 2
    $\begingroup$ Are you sure you can set such a clear cut distinction? Don't get me wrong, I completely agree that highlighting the difference between problems and algorithms is important, especially for beginners, but in practice we also say things like "the time-complexity of mergesort" or "the cost of sorting" and I wouldn't say that either of them is wrong, as long as one makes clear what exactly is the object of the sentence. $\endgroup$ – quicksort Nov 4 '17 at 19:31
  • 3
    $\begingroup$ Can you provide some reference for your claim? I have never heard of this distinction. I have also never heard anyone say a phrase like "mergesort has worst-case running time cost of.." but I am pretty sure every textbook I have opened uses the phrase "worst-case time complexity" $\endgroup$ – Sasho Nikolov Nov 5 '17 at 2:17
  • 1
    $\begingroup$ > "Cost", other than "complexity", is used for precise measures like, say, "the number of comparisons" often analysed in sorting, I have already said that in my post. no need to repeat. you do not say anything different from what has already been said. $\endgroup$ – fade2black Nov 5 '17 at 12:55
  • 1
    $\begingroup$ @fade2black Every answer should stand on its own. $\endgroup$ – Bergi Nov 5 '17 at 14:25
  • 1
    $\begingroup$ @quicksort Basically, you can not reject any Landau bound with finitely many measurements. See here for some thoughts. (Recall that falsifiability, not proof, is at the center of the scientific method. So, measurements apparently fitting a curve alone doesn't support a hypothesis -- it's about whether the measurements refute (all) other curves!) $\endgroup$ – Raphael Nov 5 '17 at 17:26
1
$\begingroup$

My approach is as following.

Computational complexity is an abstract notion having a precise mathematical definition and a field of a whole scientific research.

"Computational cost" is alternatively used for "computational complexity", though in my opinion I would not use the term "computational cost" in the formal meaning instead of "computational complexity".

The most significant difference between "complexity" and "cost" is that the "complexity" is precise mathematical measure measured using big-O notation, we usually say "space complexity" or "time complexity" where both terms "space" or "time" are abstract, i.e., by "space" we might mean RAM or HardDisk storage, while "time" might mean milliseconds, seconds, or even hours. "Cost", on the other hand, is real-life, physical, concrete measure. For example we say "it costs 2 Gigs" or "it costs 2 TB of disc space".

Let me support my point of by example. Suppose we have come up with two different algorithms solving the same problem and we have estimated exact number of operations for both algorithms, say, $n^2 + 100n$ and $0.2n^2$. We do not need to implement both algorithms in order to conclude that their complexity are equal and are $O(n^2)$. From point of view of computational complexity these algorithms have equal efficiency. However, to measure the cost of these algorithms we need to implement them, run on a computer, and measure how much time they take (in milliseconds, seconds, minutes...). This is cost and we'll obviously get different time measures for $n^2 + 100n$ and $0.2n^2$ algorithms. Thus comparing their costs we may choose a better algorithm for practical use.

$\endgroup$
  • 1
    $\begingroup$ And "cost" might include other things than just the computation time, like memory usage, hard disk usage etc. $\endgroup$ – gnasher729 Nov 4 '17 at 22:24
  • $\begingroup$ @gnasher729 Agree. My point is that by "cost" we mean usage of concrete physical resource. $\endgroup$ – fade2black Nov 4 '17 at 22:30
  • $\begingroup$ "by "cost" we mean usage of concrete physical resource" -- that is certainly not how the term is used in the AofA literature. $\endgroup$ – Raphael Nov 5 '17 at 11:44
  • $\begingroup$ "Computational complexity is an abstract notion having a precise mathematical definition" -- while it is possible to do so, most authors don't bother to do so. "Time" and "complexity" remain vague notions. Relevant parameters like, for instance, the machine model routinely remain unspecified. We have hundreds of questions this site alone which are based on confusion about these things. $\endgroup$ – Raphael Nov 5 '17 at 11:46

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.