There's so much more to CS theory than big O notation and you're in for a treat if you check out any of the below - happy to share more if people are interested.

1. https://www.amazon.com/Computational-Complexity-Approach-San...

2. https://www.amazon.com/Quantum-Computing-since-Democritus-Aa...

3. https://www.amazon.com/G%C3%B6del-Escher-Bach-Eternal-Golden...

4. https://www.amazon.com/Introduction-Theory-Computation-Micha...

What do you want to learn? Programming or CS? CS is more than just programming, and CS theory is more than just Algorithms & Data Structures.

If you want to learn about Algorithms and Data Structures and you have a strong math background, then CLRS is the book to get: http://www.amazon.com/Introduction-Algorithms-Thomas-H-Corme...

An undergraduate CS curriculum will mostly cover the parts I-VI of the book (that's around 768 pages) plus a few chapters from the "Selected Topics Chapter" (we covered Linear Programming and String Matching). Mind you, this book is very theoretical, and all algorithms are given in pseudocode, so if you don't know any programming language, you might have to go with a an algorithms textbook that is more practical. In my DS course we had to implement a Red-Black tree and a binomial heap in Java, and in my Algorithms course we only wrote pseudocode.

Maybe Sedgewick's (Knuth was his PhD advisor!) "Algorithms (4th ed)" will be a better choice for a beginner, as it shows you algorithm implementations in Java: http://www.amazon.com/Algorithms-4th-Edition-Robert-Sedgewic... (If you decide to go this route, you might as well take his two Algorithms courses on Coursera, they will really help).

There are also a bunch of Python-based introductions to computer science which have a broader focus than just teaching specific data structures and algorithms. Some of them emphasize proper program design, debugging and problem solving. I haven't read any of them, so I can't vouch for them, but here are a few of the more popular ones:

* http://www.amazon.com/Introduction-Computation-Programming-U...

This book was written to go along with John's edX course: https://www.edx.org/course/mitx/mitx-6-00-1x-introduction-co...

* http://www.amazon.com/Python-Programming-Introduction-Comput...

Oh and btw, there's also the Theory of Computation, which is a major part of CS theory. Here are a few MOOCs and recommended books on the subject:

MOOCS:

* https://www.coursera.org/course/automata

* https://www.udacity.com/course/cs313

Books:

* http://www.amazon.com/Introduction-Theory-Computation-Michae...

Sipser's book is probably the best introduction to the theory of computation, and I believe its last chapter deals with Complexity theory as well.

* http://www.amazon.com/The-Nature-Computation-Cristopher-Moor...

I loved this book very much. It has a very informal and conversational style (don't let it fool you, the problem sets can be HARD).

* http://www.amazon.com/Computational-Complexity-A-Modern-Appr...

Once you are familiar with some computation models, its time to study computational complexity and this is one of the best books on the subjects. It is used both for graduate and undergraduate courses.