Hey guys I just got a tricky homework question. I'm not looking for a straight up answer just a nudge in the right direction. Heres the question.
Your friend has dropped you at some point on Speedway Blvd, Tucson. You need to walk to the nearest bus station, but you are not sure if the nearest bus station is East or West of your location, so you are not sure which direction to go.
Let d be the distance to the nearest bus station. Suggest an algorithm that guarantees that the total distance you would walk is Θ(d). Of course, you cannot use other people, cellphones, maps etc.
Hint: go west a while, then east, then west, then .... How should each segment in one direction (assuming you don't find the station) relate to the previous segment?