Complexity nomenclature

[Timon Gehr via Digitalmars-d]

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.