Which of the following correctly states the complexity of Floyd’s cycle detection algorithm and reporting the cycle length?

• A. O(n^2) time, O(1) space
• B. O(n) time, O(1) space
• C. O(n log n) time, O(1) space
• D. O(1) time, O(n) space

Answer: (B)

The main idea is that Floyd’s cycle detection uses two pointers moving at different speeds to find a loop while using only constant extra space. When they meet inside the cycle, you can determine the cycle’s length by keeping one pointer fixed and advancing the other until it returns to the same point, counting the steps. The detection phase takes time proportional to the number of nodes you traverse, and the length-determination phase takes time equal to the cycle length. Both are bounded by the total number of elements, so the overall time is O(n). Space stays O(1) because only a few pointers are used.

Other options would imply more time or space than the algorithm actually uses, so they don’t fit the behavior of Floyd’s method.