3 ms·
* For every full iteration of the loop, TH (tortoise and hare) follows 3 links, while TT (teleporting turtle) follows 1 link.* Except the TT loop iterations ac
by argv_empty 17y ago
* For every full iteration of the loop, TH (tortoise and hare) follows 3 links, while TT (teleporting turtle) follows 1 link.*
Except the TT loop iterations accomplish half as much in terms of covering ground, so TH and TT don't take the same number of iterations.
- JoachimSchipper 17y agoIf both Tortoise and Hare have just entered a cycle of length n, the original algorithm takes n iterations before the Tortoise is caught (2n steps for the Hare, n steps for the Tortoise). Likewise, TT takes n steps (although it may take some additional steps before the turtle is teleported into the loop; once this has happened, it's n steps.)
- argv_empty 17y ago* once this has happened, it's n steps* Unless the turtle teleports some time during those n steps. The only way the turtle won't teleport during that time is if the rabbit has already taken at least n steps to get to the loop, in which case, it only eliminates up to 1/4 of the mammal moves.