Question

Door in a wall You are facing a wall that stretches infinitely in both directions.
There is a door in the wall, but you know neither how far away nor in
which direction. You can see the door only when you are right next to it. Design
an algorithm that enables you to reach the door by walking at most O(n)
steps where n is the (unknown to you) number of steps between your initial
position and the door.

please provide the solution in detail steps

Answer 1

Step1 ) The main idea here is to walk intermittently right and left going each time exponentially farther from the initial position.

Step2 ) A simple implementation of this idea is to do the following until the door is reached: For i=0,1,..., make 2i steps to the right, return to the initial position, make 2i steps to the left, and return to the initial position again. Let 2(k−1) < n ≤ 2k. The number of steps this algorithm will need to find the door can be estimated above as follows:

some math :

k-1

In the above math, the 4 is meant to calculate the number of full steps that represent a full search. So let's says we're at i = 1.

We start at x = 0. We go to 2 ^ 1 = 2. That's 2 steps. Then back to 0. Another 2 steps. Then to -2, then back to 0. A total of 8 steps, or 4 x 2 ^ 1

4 x 2 ^ i = number of steps in an unsuccessful search where we return to the origin to commence a larger search, since we can only traverse left and right, and not teleport

the kth iteration is when we find our door. The worst case is when the door is at n to the left where n = 2^k steps.

So what happens when we get into this iteration?

We start at x = 0, we go to 2^k to the right, then back to 0, then to the left to -2^k. A total traversal of 3 x 2 ^ k steps.

As to why it's compared to 7 * 2 ^ k, we know that the ith search term is 2 ^ (k - 1) or everything before. We can substitute 7*2^k with 7n based on our previous definition regarding k - 1 vs k

And we can also use the fact that 2^k = 2 x 2^(k-1) in our abstractions.

Per 2^(k−1) < n is supposed, so you can substitute 2^(k−1) by n and get 14*2^(k−1) < 14n

Hence the number of steps made by the algorithm is in O(n).