Etymology of time and space "complexity" The word choice of "complexity" in analysis of algorithms to describe temporal and spatial resource requirements has always struct me as an odd one. These are certainly useful and meaningful concepts. This question is concerned with the language used to describe them.

Colloquially, one would probably not say that insertion sort is more "complex" than radix sort.

Is the origin and rationale of this word choice known? If so, what is it?
Complexity refers to the complexity of the computation rather than the complexity of the algorithm. For example, Ritchie's Classes of predictably computable functions from 1963 "[studies] a sequence of classes of computable
functions for which a prediction of the complexity of the calculation may be
made in a comparatively simple fashion."

Hartmanis and Stearns, in their seminal 1965 paper On the computational complexity of algorithms, also use complexity in a similar sense: "One finds, however, that some computable sequences are very easy
to compute whereas other computable sequences seem to have an inherent
complexity that makes them difficult to compute." This paper is the source of the terminology, though they cite earlier papers (like Ritchie's from 1963) which had already used complexity in this sense.