Hacker News Reader

Comment by rlu | Hacker News Reader

I wonder if the title is in jest. Clicking on this link and then being greeted with a wall of text (literally! It fills my entire screen) is hardly gentle.

I'm sure it's a good read just not right now >_>

View on HN

I'd say thats why it is gentle. Most CS books will compress that content into 2-3 pages and expect you to figure the rest out as you go. On the other hand, this article doesn't require you to take some time to think about it at all, its all right there.

Fair enough

The classic CLRS Algorithms book actually starts out with a five chapter "Foundations" part that goes over computational complexity in a good amount of detail. It goes over theta, big and small O, and big and small omega notations and their properties similarly to how this article seems to. It has an entire chapter on determining the computational complexity of recurrences and another on randomized algorithms. The five chapters together are about 130 pages and probably not what I would call gentle but I found it surprisingly approachable.

CLRS has an exceptional introduction to complexity and in fact is an exceptional book on its whole. However, it is not always easy to follow for high school students who don't have a mathematical background, as it tends to get a bit formal. It's the same reason many programmers find it repulsive and wouldn't read past the first few pages. For example, the proof for the Master Theorem is clearly not that easy to follow. That's exactly the reason I wrote this article so that it's complete yet approachable to people without a mathematical background.

That being said, the section containing the proof is starred if I remember. I imagine most people, even those reading CLRS, skip over it.

Reply on news.ycombinator.com