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
