For $n\in\mathbb{N}$, let $[n]:= \{1,\ldots,n\}$. Let $\text{Fun}(n)$ denote the set of all functions $f:[n]\to[n]$. To $f\in\text{Fun}(n)$ associate a sequence $\text{seq}(f))$ defined recursively by


* $\text{seq}(f)\_1 = f(1)$, and
* $\text{seq}(f)\_{k+1} = f(\text{seq}(f)\_k)$ for all $k\in\mathbb{N}$.


Eventually $\text{seq}(f)$ will be periodic, and with $\text{per}(f)$ we denote the length of the period of $\text{seq}(f)$. By $E\_n$ we denote the *expected value* of $\text{per}(f)$ for any $f\in\text{Fun}(n)$. Explicitly, we have $$E\_n = \frac{1}{n^n}\sum\_{f\in\text{Fun}(n)}\text{per}(f).$$


**Questions.** Do we have $\lim\sup\_{n\to\infty} E\_n/n > 0$, and if yes, what is that value? If no, do we have $\lim\sup\_{n\to\infty} E\_n/\log(n) > 0$?



Expectation of period length of functions $f:\{1,\ldots,n\}\to \{1,\ldots,n\}$
The standard references here include *An Introduction to the Analysis of Algorithms* by Sedgewick and Flajolet.


The first significant reference is probably "Probability distributions related to random mappings", Bernard Harris, *Ann. Math. Statist.* 31 (1960), 1045-1062, linked to in another answer. A summary is also given in the paper "Random Mapping Statistics" by Odlyzko and Flajolet available [here](https://hal.inria.fr/inria-00075445)


The use of bivariate generating functions and saddle point methods gives the estimates for cycle length (a pre-period is followed by a cycle giving a so-called rho ($\rho$) as in Pollard's rho method). If the function has a fixed point that just becomes a cycle length of 1.


In summary the expected cycle length over your ensemble of functions is $\sqrt{\pi n/8}.$ So
$$
\lim\_{n\rightarrow \infty} \frac{E\_n}{\sqrt{n}}=constant.
$$


For whatever it's worth the expected rho-length, tail-length (initial pre-period segment of a rho) are also $O(\sqrt{n}).$ The expected component size you end up in, if you start at a random point, is $2n/3.$


