This is a simple extension of finding a friend on a single road without knowing his position.
1) n=0 2) Travel 2^n distance on the first road. If you find your friend DONE else return back to the crossing 3) Travel 2^n distance on the second road. If you find your friend DONE else return back to the crossing 4) Travel 2^n distance on the third road. If you find your friend DONE else return back to the crossing 5) Travel 2^n distance on the fourth road. If you find your friend DONE else return back to the crossing 6) n = n+1 GOTO STEP 2 Lets analyze the algo Assume d can be written as 2^a for some a ( can be extended to cases when d is not the form of 2^a) Assume the worst case of your friend being in the fourth road. Then the total distance travelled by you till you find your friend is = 4 * 2 * ( 2^0 + 2^1 + 2^2 + ....... + 2^a) // The factor of 2 at the beginning is for your returning back = 8 * (2^a+1 - 1) = 8 * (2d-1) which is O(d) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
