Complexity of determining unique elements of each cycle in a permutation

Question

It is a well known fact that a permutation is a set of cycles, and that one can find all cycles of a permutation in $O(n)$ time, where $n$ is the length of the permutation.

But suppose that we know that the number of cycles in the permutation is less than a fixed number $k$. Can we find $k$ distinct elements belonging to the $k$ cycles in less than $O(n)$ time? Clearly, if $k=1$ this is true. But is it true for all $k$?

More specifically, suppose we know that $k$ is $O(log{\text{ n}})$, does this information help in anyway? I'm interested in understanding the time complexity of this problem, but if it's possible to give an efficient randomized algorithm for this problem, that will also be interesting in itself.

I have tried to find papers on this topic without any luck so any relevant paper or material will be greatly appreciated.

Answer 1

Even for $k=2$ when the instance may have two cycles of length $n/2$, any sublinear algorithm can only build chains of length $\ll n/4$, so no deterministic algorithm can guarantee that the two vertices it outputs belong to distinct cycles.

I doubt (though I am not sure and do not have a proof) that the problem would admit a solution in sublinear expected time even for algorithms with probabilistic guarantees.