Glossary: Data Structures and Algorithms in C++

Average case

The cost you can expect in a typical run. Hash map lookups are O(1) in the average case because collisions are rare.