What are the time and space complexities of Floyd’s cycle detection algorithm?

• A. Time: O(n^2); Space: O(1)
• B. Time: O(n); Space: O(n)
• C. Time: O(n); Space: O(1)
• D. Time: O(1); Space: O(1)

Answer: (C)

Two pointers move through the list at different speeds, the fast one advancing two steps for every step the slow one takes. This setup guarantees a meeting somewhere: if there’s a cycle, they will eventually collide inside it, and if there isn’t, the fast pointer will reach the end. The number of steps before they meet (or before the end is reached) scales linearly with the number of nodes in the list, so the time complexity is O(n). The algorithm uses only a fixed number of pointers, so the extra space required is constant, O(1). This makes it the best answer for time linear in n and space constant.