<p>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. </p>

<p>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. </p>

CC BY-SA 3.0
2014-01-14T17:14:51.860Z
2014-01-14T17:14:51.860Z
Joseph Stack
<p>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.</p>

<p>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$?</p>

<p>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.</p>

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

<cc.complexity-theory><ds.algorithms><reference-request><time-complexity><randomized-algorithms>
Complexity of determining unique elements of each cycle in a permutation
Obinna Okechukwu
# Complexity of determining unique elements of each cycle in a permutation

(Asked by: username_0 on 2014-01-14)

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.

**Tags:** cc.complexity-theory, ds.algorithms, reference-request, time-complexity, randomized-algorithms


---

## 1 answers

### Answer by username_1 on 2014-01-14. Score: 3

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.


---

