Reply: Actually it is only O(n). If you double the table at each step, then for a given n the rehashing will have cost at most 1 + 2 + ... + n/4 + n/2 + n which is strictly less then 2*n, thus the O(n) complexity. The same holds for any exponential growth, like increasing table size by 25% which would be more sensible for very large tables as you want to avoid large jumps in memory use for a very small variation of the input size. The real proof can be done with geometric series.