Re:I'm Betting on HTML
by odyssey7 on Wednesday August 02, 2023 @12:20PM
(#36973006)
I guess I was thinking about indexing the visited numbers from a graph-traversal-algorithm-interview perspective instead of a CS theory one.
We can actually do it in O(1) space complexity in exchange for higher time complexity.
For i in range 1..n, compute n_i, the ith number in the hailstone iteration, and then continue the hailstone iteration n_(i+1)..n_n to see if n_i is equal to any of them. This takes us to quadratic time complexity, O(n^2), but only requires storing a single n_i at a time for cycle detection.
But then again, if you actually loop for n_max iterations without crashing, you had to reuse a number somewhere, so the explicit cycle detection isn’t really important.
We can actually do it in O(1) space complexity in exchange for higher time complexity.
For i in range 1..n, compute n_i, the ith number in the hailstone iteration, and then continue the hailstone iteration n_(i+1)..n_n to see if n_i is equal to any of them. This takes us to quadratic time complexity, O(n^2), but only requires storing a single n_i at a time for cycle detection.
But then again, if you actually loop for n_max iterations without crashing, you had to reuse a number somewhere, so the explicit cycle detection isn’t really important.