Brent’s Cycle Detection Algorithm

Anyone who’s prepped for a technical interview or who has an interest in algorithms is probably familiar with Floyd’s Tortoise and Hare algorithm for cycle detection in a linked list. The idea is that you traverse the list with two pointers, the tortoise and hare, with the hare moving twice as fast (by taking two steps at a time). If the hare laps the tortoise, the list has a cycle. It’s a cute algorithm that I’ve known about for years.

Recently, I came across a related algorithm, which I’d somehow managed to overlook, that solves the same problem: Brent’s algorithm. Like Floyd, Brent uses a tortoise and hare but the movement is different. The hare moves one step at a time and the tortoise mostly doesn’t move except that every so often it teleports to the hare’s position. If the hare ever moves to the tortoise’s position, there’s a cycle. The strategy of when to teleport the tortoise is what makes the algorithm work. There’s a nice description of the algorithm and the reason for the teleportation strategy at the link. According to Brent, his algorithm is 24% to 36% faster than Floyd’s.

Although Brent’s algorithm is usually considered more complex than Floyd’s, I find it easier to remember because the implementation details are less finicky.

This entry was posted in General and tagged . Bookmark the permalink.