IMC 2025 Problem 5

For a positive integer $n$ , let $[n]=\{1,2, \ldots, n\}$ . Denote by $S_n$ the set of all bijections from $[n]$ to $[n]$ , and let $T_n$ be the set of all maps from $[n]$ to $[n]$ . Define the order $\operatorname{ord}(\tau)$ of a map $\tau \in T_n$ as the number of distinct maps in the set $\{\tau, \tau \circ \tau, \tau \circ \tau \circ \tau, \ldots\}$ where o denotes composition. Finally, let $$f(n)=\max _{\tau \in S_n} \operatorname{ord}(\tau) \text { and } g(n)=\max _{\tau \in T_n} \operatorname{ord}(\tau) .$$ Prove that $g(n)<f(n)+n^{0.501}$ for sufficiently large $n$ .