Wouldn't it be better to replace step 5 with
Travel 2^(n+1) distance on the fourth road. If you find your friend DONE else return back to the crossing ? After you have exhausted the first three roads to a distance 2^n, there is no point to going only 2^n on the fourth road and then returning to the crossing so that you go 2^(n+1) on the first road. You can save 2^(n+1) by continuing down the fourth road for an additional 2^n before turning around. Dave On Oct 9, 9:56 am, anilkumarmyla <anilkumarm...@gmail.com> wrote: > 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 algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
