.Your friend has dropped you somewhere at a point p on Speedway Blvd. You need t
ID: 3881338 • Letter: #
Question
.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 = 3s
}
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.
Explanation / Answer
You can put s = 1 if you want but I ve kept it as s
W = 2*(s + 3s + 3*3*S + 3*3*3*s + .... (3^k) * s )
where (3^k) * s >= d i.e the last step should be d or greater
3^k >= d/s
we can say
k = ceil (log3 (d/s) )
In assymptotic notation
k = log3 (d/s)
W is a geometric series with f(n) = 3*f(n-1)
Using gp sum, we get
W = 2 * s(3^(k+1) - 1) / (2)
= (3^(k+1) - 1) * s
= ~3^k * s .... for assymptotic notation
Plug the value of k, we have
W = 3 ^ log3 (d/s) * s
= d/s * s
= d
So, W = (d) = O(d) = (d)
W = (3^(k+1) - 1) * s
3^(k-1)*s > d >= 3^k * s
dmin = 3^(k-1) * s
dmax = 3^k * s
w/dmin = (3^(k+1) - 1) / 3^(k-1))
To maximize this we have to consider large values of k so we can ignore the -1 in numerator and we have
w/dmin = 3^(k+1) / 3^(k-1) = 9 ... this is max ratio
w/dmax = (3^(k+1) - 1) / 3^(k)) ...
To minimize this, we need to consider least values of k, so put k=0
w/dmax = 2 .... this is min ratio
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.