I have 9 numbers: 4 3 2 1 0 -1 -2 -3 -4 they are placed in a circle. Consider them as addresses. that means: every element knows that it has a neighbor that is greater in value on the left, and another neighbor that is smaller in value on the right.
If for example element 0 wants to send a message to element 2, it knows it has to go 2 steps on the left. And if it is searching for -3, it knows it has to go 3 steps on the right.
Each element can perform a search for any other element.
Each element can forward the query to its adjacent neighbor.
IN that case, the worst case scenario would be for element 0 is to search for element 4 or -4, which is 4 steps either way.
Now, if I want to compare the search with this one: The same numbers are arranged in the same circle, however, the search has to go clockwise only, i.e., if I am at 0 and I want to search for 1, I have to walk through all elements clockwise.
Comparing to the first scenario, which one performs better? Should not the first one take half the time of the second one?