Asymptotic behaviour of the complete preimage cardinality for the image of a random set under iterations of mappings of a finite set

The estimation of complexity of time-memory-data tradeoff algorithms leads to the estimation problems of the complete preimage cardinality for the image of a random set under multiple iterations of mappings. We describe a probabilistic model allowing to estimate the cardinalities of the random sets considered via the number of particles and the total number of particles in the Galton–Watson process. The limits of mean values of these random variables are found.