# Does the following algorithm has amortized constant time per element?

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).

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.
• I wouldn't use the word amortized. I can say that for every possible choice of a sequence of $m$ elements, the expected complexity is $O(m)$. This is simply because the expected time for a single operation is $O(1)$, input sequences have no effect here. Nov 21, 2017 at 17:06