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.
Comments
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.