Complexity nomenclature

Xinok via Digitalmars-d digitalmars-d at puremagic.com
Thu Dec 3 18:34:01 PST 2015


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


More information about the Digitalmars-d mailing list