Time complexity of hash table, separate chaining (average case)

For a hash-table with separate chaining, the average case runtime complexity for insertion is O(n/m + 1) where n/m is the load factor and + 1 is for the hash function.

Could this be considered equivalent to O(n/m) under big-O notation since 1 is just a constant, and any multiple of n/m can bound n/m + 1?

> the average case runtime complexity for insertion is O(n/m + 1)

I normally simplify and remove lower-order components when expressing complexity in big-O notation, rather than having things in there that are yet to be simplified. I'd suggest you say "the number of operations" is n/m + 1 (or +2 perhaps, if the insertion itself can be considered an operation), then consider how to express a simplified big-O complexity, as you're indeed doing with this question:

> Could this be considered equivalent to O(n/m) under big-O notation since 1 is just a constant, and any multiple of n/m can bound n/m + 1?

The +1 is indeed superfluous. Your reasoning is correct. Another way of explaining it that might or might not help: no matter how slow it is to hash, if you were doing operations with even O(log(log(K)) complexity for some variable K, that K-related value would - as K increases - eventually grow large enough that the +1 would be irrelevant.

The more interesting question is whether it's meaningful to write O(n/m), or should you be simplifying to O(n) or O(1)? To answer that, let's think of n/m as the load factor: if we keep doing insertions, how will our load factor keep changing? There are two possibilities:

• if we aren't actively doing something to keep the load factor in a particular range, then it will grow linearly with insertions; if we're not varying the bucket count at all, then the m factor is constant and hence the complexity simplifies to O(n)

• if we are growing the hash table as we go, then while we don't have
  to, why wouldn't we keep it in some linear proportion to n (i.e.
  keeping the load factor beneath some fixed value), such
  that the insertion complexity is O(1)? [That's the obvious
  thing to do, and what every implementation I've ever seen that can
  resize actually does do.]

So, the most-simplified (and therefore correct) expressions of the big-O complexity of further insertions is either O(1) (for resizing hash tables), or O(N) for fixed-bucket-count tables with load factors much greater than 1.