The Lazy Builder’s Complexity Lesson
“The Lazy Builder’s Complexity Lesson” begins:
Bob the lazy builder doesn’t bother sorting his nails, screws, nuts, bolts, washers etc. They’re all muddled together in the bottom of his toolbox. Whenever Bob takes on a new job, he rummages around in his toolbox to see if he has everything he needs.
Despite this lack of organization, Bob’s services are in demand. His business is growing and so is his toolbox, to the point that rummaging around in it is taking up too much of his time. This article discusses various algorithms Bob could use and compares their efficiency. We shall make use of the C++ Standard Library and consider what its complexity guarantees mean to us in practice.
The full article is available online at The C++ Source. A zip archive of the supporting source code can be found here.
Articles