complexity of a randomized search algorithm

Question

Consider the following randomized search algorithm on a sorted array a of length n (in increasing order). x can be any element of the array.

size_t randomized_search(value_t a[], size_t n, value_t x)
    size_t l = 0;
    size_t r = n - 1;
    while (true) {
        size_t j = rand_between(l, r);
        if (a[j] == x) return j;
        if (a[j] < x) l = j + 1;
        if (a[j] > x) r = j - 1;
    }
}

What is the expectation value of the Big Theta complexity (bounded both below and above) of this function when x is selected randomly from a?

Although this seems to be log(n), I carried out an experiment with instruction count, and found out that the result grows a little faster than log(n) (according to my data, even (log(n))^1.1 better fit the result).

Someone told me that this algorithm has an exact big theta complexity (so obviously log(n)^1.1 is not the answer). So, could you please give the time complexity along with your approach to prove it? Thanks.

---

Update: the data from my experiment

log(n) fit result by mathematica:

log(n)^1.1 fit result:

Answer 1

If you're willing to switch to counting three-way compares, I can tell you the exact complexity.

Suppose that the key is at position i, and I want to know the expected number of compares with position j. I claim that position j is examined if and only if it's the first position between i and j inclusive to be examined. Since the pivot element is selected uniformly at random each time, this happens with probability 1/(|i - j| + 1).

The total complexity is the expectation over i <- {1, ..., n} of sum_{j=1}^n 1/(|i - j| + 1), which is

  sum_{i=1}^n 1/n sum_{j=1}^n 1/(|i - j| + 1)
= 1/n sum_{i=1}^n (sum_{j=1}^i 1/(i - j + 1) + sum_{j=i+1}^n 1/(j - i + 1))
= 1/n sum_{i=1}^n (H(i) + H(n + 1 - i) - 1)
= 1/n sum_{i=1}^n H(i) + 1/n sum_{i=1}^n H(n + 1 - i) - 1
= 1/n sum_{i=1}^n H(i) + 1/n sum_{k=1}^n H(k) - 1  (k = n + 1 - i)
= 2 H(n + 1) - 3 + 2 H(n + 1)/n - 2/n
= 2 H(n + 1) - 3 + O(log n / n)
= 2 log n + O(1)
= Theta(log n).

(log means natural log here.) Note the -3 in the low order terms. This makes it look like the number of compares is growing faster than logarithmic at the beginning, but the asymptotic behavior dictates that it levels off. Try excluding small n and refitting your curves.