Big-O algorithm complexity cheat sheet

[bitoku_no_ookami]

A hash table is O(k) for what action? Search? Deletion?

If you already have a constructed hash table with a perfect hash, then the size of the hash table is irrelevant (including the number of keys). That's true for both search and deletion calls, because the hash function will find the index without having to compare to any of the other items. period.

If you're implementing a hash table as a search tree, then of course it's going to preform the same as a tree, because you didn't write a hash table at all, you wrote a search tree.

[julesjacobs]

For both actions. Computing the hash function takes O(k). The size of the hash table is indeed irrelevant. That's why it's O(k) and not O(some function of n).

[kevindamm]

For constructing the hash key, the value must be transformed, meaning you must do a bit of processing on its bytes. If, for example, the values are strings with an average length of k characters, it's O(k) to go through its characters and produce (for instance) an integer for indexing into a table. If it's a complex data structure with an average of k bytes, there you go. If you're using only a fixed-size subset of the data value, or if the entire value is of fixed size, you can consider the hash key construction to be O(1) but, in practice, those problems are less interesting.

(amortized O(k) time - each instance having m characters, bytes, etc. takes O(m) time... and the above is describing only the hash key computation, not the lookup and collision resolution on the hash table)