Door in an infinite wall algorithm

Question

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.

Answer in book:

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

Hence the number of steps made by the algorithm is in O(n). (Note: It is not difficult to improve the multiplicative constant with a better algorithm.

Where I get lost:

I get lost when it gets to the sum. Can someone please explain to me how the sum works?? Like why did they multiply the 2^k and 2ⁱ by 4 and 3? Why are they comparing it to < 7·2^k? How did it equal 14·2^(k-1) which is compared to < 14n. I think I get the fact that n = 2^(k-1) which would explain the last past of the sum but so many questions.

Answer 1

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 @AbcAeffchen 2^(k−1) < n is supposed, so you can substitute 2^(k−1) by n and get 14*2^(k−1) < 14n