The algorithm is a randomized algorithm and we're assuming we're picking a good hash. The probability of that event is exponentially vanishing, so, in expectati

The algorithm is a randomized algorithm and we're assuming we're picking a good hash. The probability of that event is exponentially vanishing, so, in expectation (which is the runtime we're looking for, as we are analyzing a randomized algorithm based on rejection sampling) it is O(1). In the worst case analysis of this rejection-sampling algorithm, the time for table look up and insertion doesn't even factor in since you'll have infinite run-time.