Your friend has dropped you somewhere at a point p on Speedway Blvd. You need to walk to the nearest bus station, but you are not sure if the nearest 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. Of course, d is not known to you in advance. Let w be the distance you walked (in the worst case) until reaching the station.

The following algorithm has proposed

Figure 3: The lake. You have landed at p, and wish to swim to the shore. The nearest point of the shore is q. (credit: ClipPanda.com)

set s = 1 // 1 foot

while( not reached the bus station ) {

walk a distance of s East return to p walk a distance of s West return to p s = s + 1

}

Assume d is much larger than 1 foot. Express w (as a function of d). Is it true that w = (d) ? Is it true that w = O(d) ? What is the ratio w/d in the best case ? What is the ratio w/d in the worst case ? Prove your answers.

Clarification The best case occurs when the bus station is positioned such that the ratio w/d is the smallest possible value. The worst case occurs when the bus station is positioned such that the ratio w/d is as large as possible.