Find a hole while travelling along an infinite wall There is an infinite wall with a hole somewhere, you are placed on that wall at an unknown position. Let the distance between your initial position &amp; the hole be $x$. Find the average distance traveled in terms of $x$ until you find the hole. What's the complexity of this problem in terms of $x$ and how does an algorithm look like that solves it?
If you can go only left or right, than you can do the following strategy:

DIRECTION = Right
For i = 0 to infinity do:
    Go 2^i steps to DIRECTION.
    Go back to the initial place.
    CHANGE_DIRECTION
    STOP if you found the hole


If the distance between the start place and the hole is n, you will find the hole within O(n) steps. You can easily calculate the exact average number of steps given this algorithm.