Does the solution have to be deterministic? If an adversary places the hotel after looking at my algorithm, my first inclination is introduce uncertainty into my search.
Randomising the length of the first step will improve on the constant factor by about 2. Similar analysis to the non-adversarial case, and with the same ETA I just added to my earlier comment.
Ah yes, OK, essentially the same randomization helps against an adversary when you’re growing exponentially as when you’re growing only linearly. Fair enough.
Does the solution have to be deterministic? If an adversary places the hotel after looking at my algorithm, my first inclination is introduce uncertainty into my search.
No. But you can’t do better than O(k) anyways, and you can do O(k) deterministically.
Randomising the length of the first step will improve on the constant factor by about 2. Similar analysis to the non-adversarial case, and with the same ETA I just added to my earlier comment.
If you make the run lengths increase exponentially instead of linearly then you get O(k) unconditionally.
I know. I was improving the constant factor.
Ah yes, OK, essentially the same randomization helps against an adversary when you’re growing exponentially as when you’re growing only linearly. Fair enough.