On 12/04/2015 03:34 AM, Xinok wrote:
On Friday, 4 December 2015 at 01:55:15 UTC, Timon Gehr wrote:
Regarding nomenclature, it would be awesome if we could call this
"running time" instead of "complexity". Algorithms have running times
and memory usages. Problems have (time and space) complexities. I know
that calling running time 'complexity' is awfully popular outside of
actual complexity theory papers. I don't really understand what
calling it 'complexity' actually buys though.
I've seen you mention this before, and while you may be correct, the
term "complexity" is so widely applied to algorithms that it's not worth
going against the norm. For the vast majority of computer scientists,
when they hear the term "time complexity", they immediately understand
it as running time.
I understand what is meant, but it is painful, much like when somebody
uses "literally" but actually means "figuratively". :-)
In fact, what I've seen most often is that
algorithms have complexities and problems fall into a *complexity
class*. For example, just take a look at the Wikipedia page on time
complexity:
https://en.wikipedia.org/wiki/Time_complexity
It's a schizophrenic article. It mostly uses the standard terminology
starting from this section:
https://en.wikipedia.org/wiki/Time_complexity#Constant_time
I guess the article has multiple authors, only some of which are
complexity theorists.
