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\).
68W40 Analysis of algorithms
68U20 Simulation (MSC2010)
68W05 Nonnumerical algorithms