You are facing a high wall that stretches infinitely in both directions. There is a door in the wall, but you don't know how far away or in which direction. It is pitch dark, but you have a very dim lighted candle that will enable you to see the door when you are right next to it. Suppose n is the (unknown to you) number of steps between your initial position and the door. For both algorithms, the input is the high wall that stretches infinitely in both directions. For the output, you can simply return that the door is found. Remember, a complete answer includes an algorithm description, an algorithm, and an analysis.

(a) Give a O(n²) algorithm that enables you to reach the door.

(b) Give a O(n) algorithm that enables you to reach the door.