The amortization is the average and is O(1). The claim is that the worst case (when the table becomes relatively saturated and a resize is required) is O(N^0.5). I don't really buy that and the supplied link doesn't really make that claim either. By the argument in that link, it should be O(N^1.5) for rehashing. (Usually we think that copying N items is O(N), but he makes an argument from physics which I haven't thought through.)