For folks who genuinely love math (I do!), there's a great but little-known book by Hardy called Orders of Infinity that can help readers grok the possibilities of big-oh notation. It's not about algorithms, but about getting a solid understanding of the many ways functions can behave as n goes to infinity. As a bonus, it's a short (< 100 page) book.

If you're more of a CS person than a mathy, I recommend Sipser's Introduction to the Theory of Computation. This one is written in friendly yet precise terms, and I found it a pleasure to read.