Return to Answer

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(\_)$".

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(\_)$".

I prefer to use the terms like this:

• The term "complexity" applies to problems. For instance, you can say "sorting has $\Theta(n \log n)$ worst-case time complexity (in the comparison model)".

• Algorithms have costs; you would say "Mergesort has a worst-case running-time cost in $\Theta(n \log n)$ (under the RAM model)".

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, it's the $\Theta$-class of dominant cost measures that is often equated with an algorithm's "(time) complexity". However, I consider this practice confusing and thus harmful (cf. item 1), and prefer to say "[cost measure] is in $\Theta(\_)$".

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(\_)$".

Often misused, the term "complexity" applies to problems. For instance, you can say "sorting has $\Theta(n \log n)$ worst-case time complexity (in the comparison model)".

Algorithms have costs; you would say "Mergesort has a worst-case running-time cost in $\Theta(n \log n)$ (under the RAM model)".

Note that "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. It's the $\Theta$-class of dominant cost measures that is often equated with an algorithm's "complexity" -- I consider this practicte confusing and thus harmful, and prefer to say "the cost measure is in $\Theta(\_)$" (which is mathematically precise).

Furthermore, 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.

Finally, let me note that the analysis of cost measures can yield testable hypotheses, if it's more precise than Landau bounds. "Complexity" results are not testable.

I prefer to use the terms like this:

• The term "complexity" applies to problems. For instance, you can say "sorting has $\Theta(n \log n)$ worst-case time complexity (in the comparison model)".

• Algorithms have costs; you would say "Mergesort has a worst-case running-time cost in $\Theta(n \log n)$ (under the RAM model)".

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, it's the $\Theta$-class of dominant cost measures that is often equated with an algorithm's "(time) complexity". However, I consider this practice confusing and thus harmful (cf. item 1), and prefer to say "[cost measure] is in $\Theta(\_)$".