Consider a hashmap. Hashmaps give expected constant access time, and amortised constant access time on the condition that their size grows at a sufficient rate

Consider a hashmap. Hashmaps give expected constant access time, and amortised constant access time on the condition that their size grows at a sufficient rate and that the hash function is a universal hashing function. This is parametric. Assume that you use a linkedlist for collisions, then for some growth rates, your cost of access is not constant, and is certainly at most O(n). The point being that the universal hashing function has 1/m probability of collision; if your growthrate is bad. Then m << n, which turns the expected time from constant to at most O(N) because m grows slower than N.