with history questions there are typically subtle nuances and its not easy to determine a particular paper that introduced a particular concept because it tends to be spread over many contributors and is sometimes rediscovered independently when obscure early references dont necessarily disseminate (fundamental ideas are like that). but the history basically goes something like this: Landau notation is an old mathematical formalism (1894/ Bachman) which was imported into CS as a "key concept" around the early 1970s. by the mid 1970s this was somewhat accepted as in your Knuth reference and Knuth himself was involved in spreading this concept.
interestingly its import into CS was probably closely related to the P vs NP vs Exptime distinctions uncovered in early 1970s which were highly influential/ heralded in the field. it was Cobham/ Edmonds who started to define the class P in early 1970s. there were early proofs about Exptime and Expspace by Stockmeyer/ Meyer. the Cook-Levin theorem (1971) showed the core relevance of P vs NP time, immediately supported by Karp (1972).
an early mathematician who worked in number theory but also on the edge of computer science was Pocklington. as in  it points out:
However, H. C. Pocklington, in a 1910 paper, analyzed two algorithms for solving quadratic congruences, and observed that one took time "proportional to a power of the logarithm of the modulus" and contrasted this with one that took time proportional "to the modulus itself or its square root", thus explicitly drawing a distinction between an algorithm that ran in polynomial time versus one that did not.
another early pioneer in analyzing complexity of machine-based algorithms for number theory, ie factoring, was Derrick Lehmer, professor of mathematics at University of California, Berkeley, and built/ analyzed factoring "algorithms" (sieve based implementations) as early as the 1920s and its possible he may have described something like computational complexity wrt factoring in an informal way.
yet another case is a "lost" 1956 letter by Godel to von Neumann talking about complexity measurements of steps f(n) of a machine to find proofs of size n.
 Big O notation history / wikipedia
 Word problems requiring exponential time. / Stockmeyer, Meyer (1973)
 P time class history / wikipedia
 Cook-Levin theorem / wikipedia
 Karps 21 NP complete problems / wikipedia
 Lehmer factoring machine/ sieve / wikipedia
 Godels lost letter / RJLipton