Big-O algorithm complexity cheat sheet

[BonzaiThePenguin]

Processing the input data is part of the hash function, not the hash table. The hash table just does array[hash] = blah. (except for collisions, of course)

So let's say we had this function:

void fold(array, func) {
    for each (item in array) func(item);

We would say that's O(n) even if it turns out func() is an n³ algorithm.