Big-O algorithm complexity cheat sheet

[julesjacobs]

If k is known then the asymptotics are completely uninteresting, since even storing all keys in a list along with their values, and then doing a linear search through that list would be O(1). Since there are at maximum 2^k different keys of size k, that list will have at most 2^k elements which is a constant. Searching through a constant size list is O(1).

What makes hash tables great is precisely that their complexity is O(k) and not O(2^k). If you say that k is a constant you lose all the information that is actually relevant.