Recognize expected O(1) map get

Updated Oct 7, 2026

ADT get, put, delete, contains-key are expected O(1). contains-value, min-key, and find the key for this value are O(n). A loop of n gets is O(n) total, not O(1).

What to focus on

If you binary-search a sorted array of keys you are in a different ADT. If you scan the original list for each query you did not use the map.

Worked examples

a = [4, 1, 9] as {4:2,1:8,9:3}, get 1

a = [4, 1, 9] as a map, get n keys

a = [4, 1, 9] as {4:2,1:8,9:3}, find key with value 8

Try it

Write labelCost(op). op is "get", "nGets", or "findKeyForValue". Return the cost label. Only a single get is expected O(1) per call. a = [4, 1, 9] as {4:2,1:8,9:3}, get 1 → expected O(1). a = [4, 1, 9] as a map, get n keys → O(n) total. a = [4, 1, 9] as {4:2,1:8,9:3}, find key with value 8 → O(n), not a get.

keys are integers. The map is non-empty.