It depends on what you want. I've only read the first volume so far, but I would say that it's definitely appropriate for an intro to CS since you have the math background. I would definitely not recommend it to most people since the math is pretty dense and not all necessary (though very interesting). If you're familiar with combinatorics and stats, then it won't be too bad.

As a CS book, it teaches a lot of good CS concepts and techniques very thoroughly, and it analyzes the performance of algorithms very precisely. You'll not only use Big O notation, but you'll also figure out some of the constants. So, if your interest is in computer science proper, then this is a great introductory book.

On the other hand, if your goal is to be able to write programs, then definitely jump into using a language. Go find a book on a language and just start using the language to solve problems. After you get past the basics of programming, you'll start to see all the applications to math (especially discrete math). I've heard Structure and Interpretation of Computer Programs is a good book, and I plan to read it next semester, so maybe that's a good one for you. It uses Scheme (a Lisp) as the programming language, so the parallels with math are very clear.