Existence of a random integer in a sorted circularlly linked list

Question

This is my task:

There exists a circular and sorted linked list with n integers. Every element has a successor pointer to the next bigger item. The biggest item in the list points back to the smallest item. Determine whether a passed in target item is a member of the list. You can access an item in the list in two ways: You can follow the next pointer from an item that has already been accessed, or you can use a function "RAND" that returns a pointer to a uniformly random item in the list. Create a randomized algorithm that finds the target item and makes at most O(√n) passes in expectation and always returns the right answer.

I'm unsure about how to construct an algorithm in the required time complexity. I think it has something to do with calculating and storing some set of sums in the list but can't figure that step out.

Answer 1

The solution is based on the Dave's comment:

Use RAND sqrt(n) times, storing the largest element < target. Show that this is expected to be within sqrt(n) of the target.

Denote by i index of biggest element in the list which less to the target element.

Now lets compute expectation of hitting element in a range (i - sqrt(n), i] in sqrt(n) trials. On every trial the probability of hitting the range is range length divided by the list length, which is sqrt(n)/n = 1/sqrt(n), so

E = 1/sqrt(n) * sqrt(n) = 1.

So we expect to check presence of the target element by choosing the biggest element which is smaller than the target in our sqrt(n) trials and then advance linearly for sqrt(n) items.