# zbMATH — the first resource for mathematics

Testing of sequences by simulation. (English) Zbl 1218.68208
Summary: Let $$\xi$$ be a random integer vector, having uniform distribution ${\mathbf P}\{\xi=(i_1,i_2,\dots,i_n)=1/n^n\}\text{ for }1\leq i_1,i_2,\dots,i_n\leq n.$
A realization $$(i_1,i_2,\dots,i_n)$$ of $$\xi$$ is called good if its elements are different. We present algorithms, Linear, Backward, Forward, Tree, Garbage, Bucket, which decide whether a given realization is good. We analyse the number of comparisons and running time of these algorithms using simulation gathering data on all possible inputs for small values of $$n$$ and generating random inputs for large values of $$n$$.
##### MSC:
 68W40 Analysis of algorithms 68U20 Simulation (MSC2010) 68W05 Nonnumerical algorithms