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.