What do you mean by comprehensive? The problem i see is that "comprehensive" also mean "rather complicated". I have a great algorithms book i used in college. It talks a lot about data structures, sorting, and various other topics. But, it assumes you know the fundamentals of programming. It also get VERY math-y. Much of this stuff is not what you need when you are just beginning to learn programming.
And any book on the fundamentals of programming is most likely not going to go into big-0 notation and how to calculate it.
Another point - a good OOD book is NOT going to talk about Java. Good OOD is language independent.
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
What I've seen of Head First Design Patterns is very good. If that keeps your interest and you want more, I often recommend Robert Martin's Agile Software Development, which he calls PPP for the subtitle Principles, Patterns, Practices. I probably wouldn't suggest PPP until you've gotten a solid start and still want more.
A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi