4
$\begingroup$

I understand in Floyd’s cycle, you are finding a cycle in a linked list by moving two counters- one by a factor of 2, other by a factor of 1. In Brent’s you are basically doing the same but the one factor moves by multiplying 2 instead by merely adding 2. Is there any math explanation behind why Brent’s is faster than Floyd’s?

$\endgroup$

migrated from mathoverflow.net Sep 7 '16 at 12:01

This question came from our site for professional mathematicians.

  • 1
    $\begingroup$ Welcome to CS.SE! What research have you done? The Wikipedia article describes Brent's algorithm, says it's at most a constant-factor faster, and provides references for the claim that it is a bit faster: en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algorithm Have you read the references that Wikipedia cites? We expect you to do research and to exhaust all reasonable resources on your own before asking, and to show us in the question what research you've found. This helps us give you better answers. $\endgroup$ – D.W. Sep 7 '16 at 5:47
  • 3
    $\begingroup$ Have you read Brent’s paper? maths-people.anu.edu.au/~brent/pd/rpb051i.pdf Section 4 gives an average-case analysis and comparison with Floyd's algorithm. $\endgroup$ – Robin Houston Sep 7 '16 at 7:22
  • $\begingroup$ hi, I have read his paper, but I still cannot seem to make sense of it :( $\endgroup$ – javanewbie Sep 7 '16 at 13:00
  • $\begingroup$ I have read the paper, but I still do not understand certain parts of the algorithm, such as the random number m, etc. $\endgroup$ – javanewbie Sep 7 '16 at 13:00
  • 2
    $\begingroup$ If you've read the paper, then you should be able to ask a more specific question about it. What parts do you understand? What's the first part you got lost on? Can you summarize what you do understand, then ask about one aspect that has you confused? It's also helpful to share what your thoughts on that part are (e.g., what guesses have you been able to come up with for what the answer might be, and why do you think they are wrong). I encourage you to edit the question to ask something more specific and focused; that makes it more likely we can give you an answer you'll find helpful. $\endgroup$ – D.W. Sep 7 '16 at 17:59
3
$\begingroup$

The performance of cycle-finding algorithms depends on two parameters $m,n$. Here $n$ is the length of the cycle, and $m$ is the initial position of the cycle. For example, consider the sequence $$ 2, 3, 5, 6, 5, 6, 5, 6, \ldots $$ Here the cycle is $5,6$ and so $n = 2$. The first index of the cycle (assuming $x_1 = 2$ and so on) is $m = 3$.

We assume that the sequence is generated by repeatedly applying some function $f$. We measure the complexity of cycle-finding algorithms by the number of applications of $f$.

According to Brent's paper, the complexity of Floyd's algorithm is between $3\max(m,n)$ and $3(m+n)$, and that of Brent's is at most $2\max(m,n) + n$, which is always better than $3\max(m,n)$.

A perhaps more meaningful comparison is what happens in the average case. In this case we assume that $f$ is a random function on a universe of size $N$ (the starting point doesn't matter in this case). Knuth showed that the expected running time of Floyd's algorithm is roughly $3.0924\sqrt{N}$, whereas Brent's algorithm runs in expected time roughly $1.9828\sqrt{N}$, as worked out in Brent's paper.

For more details, take a look at Brent's paper and the references therein.

$\endgroup$
  • $\begingroup$ Thank you for this explanation! What is it about Brent's Cycle that makes it faster? I am trying to read his paper, but as a high school student, I am struggling with a lot of the syntax and symbols and finding it hard to make out the inner workings of Brent's algorithm itself. $\endgroup$ – javanewbie Sep 7 '16 at 15:03
  • 1
    $\begingroup$ It's a different algorithm, and happens to be faster. For anything more you'll have to understand the math. There's no going around it. If you're still struggling with the math, wait for a few years and then try again. $\endgroup$ – Yuval Filmus Sep 7 '16 at 15:08
  • $\begingroup$ Is it just a coincidence that it's faster? I know the basic workings of the algorithm- Brent's counter increases by powers of 2, Pollard's counter increases by only a constant of 2. Why are powers of 2 superior? $\endgroup$ – javanewbie Sep 7 '16 at 15:10
  • $\begingroup$ Actually you can use any powers (and probably other sequences as well), and to get the best average case performance you actually need to use powers of some other number, as detailed in Brent's paper. $\endgroup$ – Yuval Filmus Sep 7 '16 at 15:13
  • 1
    $\begingroup$ I also think you're misrepresenting the difference between the two algorithms. Perhaps you should try to work out the worst-case analysis yourself to see why Brent's algorithm is better in that regard. $\endgroup$ – Yuval Filmus Sep 7 '16 at 15:13

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.