Does the following algorithm has amortized constant time per element?

Question

Consider the following streaming ``algorithms'':

1. When an element $x$ arrives, flip a fair coin until it shows ``heads''.
2. Fix a random hash function $h:U\to\{0,1\}^\infty$ (i.e., it maps elements into infinite bit strings). When an element $x$ arrives, do $LZ(h(x))$ operations, where $LZ$ is the number of leading zeros in $h(x)$. Notice that for any element $x$, the distribution of time spent is same as in (1).

Clearly, both algorithms spend in expectation $O(1)$ time per element, and their worst case is unbounded.

The key difference is that algorithm (1) makes the coin flips independently for each arrival, and (2) fixes a distribution such that every time $x$ arrives, it spends the same amount of time.

(1) should clearly be called amortized constant time. (2), however, might spend more than constant time if the input consists of many appearances of an element $x$ for which $LZ(h(x))$ is large.

Would you consider (2) to have an ``amortized'' constant time?

If not, is there anything more accurate than saying that it has "expected constant time per element"?

---

While these ``algorithms'' are clearly useless, there exist algorithms with a runtime similar to (2) (e.g., see here).

Answer 1

I wouldn't use the word amortized in this context, since there is no change of state between different operations (this is unlike classic examples for amortized analysis such as dynamic arrays). In that case amortized and worst case analysis will agree.

The first case is a randomized algorithm, so you can talk about the expected or worst case complexity (where in the former, the expectation is over the inner randomness of the algorithm). The worst case complexity is unbounded, while the expected number of operations is indeed constant.

In the second case, you have a fixed function $h$ which you use for all inputs, so again there isn't actually a change of state and thus there is no sense in talking about a recurring bad input. Note that the algorithm is not randomized (it does not toss coins after seeing the input), so the question you're looking for now is what is the average case complexity of your algorithm, where the expectation is over the choice of $x$ (relative to some distribution over $U$), and the random choice of $h$. For a completely random $h$, you will get the same answer as in the first case.