I try to understand algorithm from this Wikipedia article. Initially it is talking about some function f. I specifically getting problem in that part. Below is the paragraph which is quite mathematical. Can anyone explain me that?

For any function $f$ that maps a finite set $S$ to itself, and any initial value $x_0$ in $S$, the sequence of iterated function values

$x_0, x_1 = f(x_0), x_2 = f(x_1), ..., x_i $

must eventually use the same vale twice: there must be some pair of distinct indices $i$ and $j$ such that $x_i$ = $x_j$. Once this happens, the sequence must continue periodically, by repeating the same sequence of values from $x_i$ to $x_{j−1}$. Cycle detection is the problem of finding $i$ and $j$, given $f$ and $x_0$.

  • $\begingroup$ Does this answer your question? Floyd's Cycle detection algorithm | Determining the starting point of cycle $\endgroup$
    – Nathaniel
    Jan 2 at 10:08
  • $\begingroup$ Actually I am not interested in Floyd's cycle detection algorithm but I was not able to understand the 2nd paragraph in the above image. $\endgroup$ Jan 2 at 13:57
  • $\begingroup$ Please don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. $\endgroup$
    – Nathaniel
    Jan 2 at 14:00
  • $\begingroup$ I hope it fine now? @Nathaniel $\endgroup$ Jan 2 at 14:20
  • $\begingroup$ What do you understand? Just asking us to re-explain a paragraph often isn't a good fit here. I worry that if you didn't understand that explanation, you won't understand another one, either. Please give us something to work with, so we know what you do understand and what specifically confuses you about that explanation. $\endgroup$
    – D.W.
    Jan 3 at 2:53

Suppose $S$ is a set of size $n$. Then considering the values $x_0$, $x_1$, …, $x_n$, using the pigeonhole principle, there must be $0\leqslant i < j \leqslant n$ such that $x_i = x_j$ (because all values $x_k$ are in the set $S$, which contains $n$ distinct values).

Therefore, $x_{j+1} = f(x_j) = f(x_i) = x_{i+1}$, $x_{j+2} = f(x_{j+1}) = f(x_{i+1}) = x_{i+2}$, and so on.

It means that the values $x_j$, $x_{j+1}$, …, $x_{2j-i-1}$ will be exactly the values $x_i$, $x_{i+1}$, …, $x_{j-1}$. There is indeed a cycle of length $j-i$ starting at index $i$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.