Here is the problem: You are facing a high wall that stretches infinitelyin both

Question

Here is the problem:
You are facing a high wall that stretches infinitelyin both directions. There is a door in the wall, but you don't knowhow far away or in which direction. It is pitch dark, but you havea very dim lighted candle that will enable you to see the door whenyou are right next to it. Show that there is an algorithm thatenables you to find the door by walking at most O( n) steps, wheren is the number of steps that you would have taken if you had knownwhere the door was and walked directly to it. So am I supposed to research into existing algorithms with arunning time of O(n)? Or am I supposed to create my own algorithmto solve this problem? I don't really know how to tackle this problem. Some helpwould be great. Thanks Here is the problem:
You are facing a high wall that stretches infinitelyin both directions. There is a door in the wall, but you don't knowhow far away or in which direction. It is pitch dark, but you havea very dim lighted candle that will enable you to see the door whenyou are right next to it. Show that there is an algorithm thatenables you to find the door by walking at most O( n) steps, wheren is the number of steps that you would have taken if you had knownwhere the door was and walked directly to it. So am I supposed to research into existing algorithms with arunning time of O(n)? Or am I supposed to create my own algorithmto solve this problem? I don't really know how to tackle this problem. Some helpwould be great. Thanks

Explanation / Answer

Start by taking 1 step to your left. Turn around and take 2steps to your right. Turn around and take 4 steps back in theoriginal direction. Turn around and take 8 steps back to yourright. Turn around and take 16 steps to your left, etc. Now, let'ssay you find the door 9 steps to the left of where you started. Youcan now compare the two. Had you known where the door was you wouldhave walked 9 steps. Instead, you walked 13 + 8 + 4+ 2+ 1 = 29steps. However this is less than 4 times the ideal. In this case, nis 9 (the amount you should have walked). Now imagine the door was5 steps to the right of where you started. In this case you shouldhave walked 5 but you walked 8 + 4 + 2 + 1 = 15 steps (since youdidn't find it til the time you walked 8 steps the right). This isless than 4 times the ideal amount. By showing that by using thissystem, your total walk time is always less than 4 times the idea,you are showing that your system works in 4n, which is an O(n)algorithm.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---