Cycle Detection

In computer science, cycle detection is the algorithmic problem of finding a cycle in a sequence of iterated function values.

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

must eventually use the same value twice: there must be some ij such that xi = xj. Once this happens, the sequence must continue by repeating the cycle of values from xi to xj−1. Cycle detection is the problem of finding i and j, given ƒ and x0.

Read more about Cycle Detection:  Example, Definitions, Computer Representation, Algorithms, Applications

Famous quotes containing the word cycle:

    The cycle of the machine is now coming to an end. Man has learned much in the hard discipline and the shrewd, unflinching grasp of practical possibilities that the machine has provided in the last three centuries: but we can no more continue to live in the world of the machine than we could live successfully on the barren surface of the moon.
    Lewis Mumford (1895–1990)