If you want a very mathematical approach, two books I used together to learn about computational complexity and algorithms were Concrete Mathematics (Graham, Knuth, and Patashnik) and The Art of Computer Programming (Knuth).
Neither of these books rely on any real-world programming languages, but if you can read and understand even a significant part of them, you will be in good shape. Depending on your background, that may be a difficult task, but it is worth it in my opinion.
**Edit:** Emulators exist for Knuth's MIX and MMIX, but the languages in _The Art of Computer Programming_ are not "real-world" in any practical sense.