I think you're right. Moreover, the related Landau big-O notation was used in real analysis before the algorithm analysis big-O notation was in use (Landau died a month after Knuth was born, in the thirties).

Related number theorists had notations for big-Omega and little-o as well, but I think big-Theta was pretty much Knuth's idea.

Knuth's summary of the history of these notations is at:

http://www.phil.uu.nl/datastructuren/10-11/knuth_big_omicron...

(Parenthetically, one look at the above link and you know why Knuth was driven to write TeX.)