Etymology of time and space "complexity"
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.