How to calculate time complexity of a randomized search algorithm?

Question

Example: Finding an element from a sorted array

Let's say we have an algorithm that accepts a sorted array of length N as its input. Then in each iteration it randomly selects an element from the array and performs the following operation:

if (value == A[randomIndex])
   // element found
else if (value < A[randomIndex])
   // check the left subarray of the randomIndex
else
   // check the right subarray of the randomIndex

This is similar to binary search but instead of selecting a mid index of the low and high index, we simply select a random index between low and high index.

Can anyone please provide the time complexity for this algorithm in worst, average and best case with a simple explanation for each?

Answer 1

Best case is $O(1)$, that is when you find the element in the first check.

Worst case is $O(n)$, and it happens when the element is in the first position, and in each check you get the last position, thus going through the whole array.

Average case is a little bit more tricky to get, since we need to solve a recurrence to get the expected value. Let $T(n)$ be the expected time for an array of size n. The pivot is chosen randomly, so each posible pivot has a probability $p = \frac{1}{n}$. So, we have this:

$T(n) = T(1)/n + T(2)/n + ... + T(n-1)/n + 1$

We add that 1 at the end, because that's the constant time we have for checking at each step. Now we multiply each side by n:

$nT(n) = T(1) + T(2) + ... + T(n-1) + n$

Which also gives:

$(n-1)*T(n-1) = T(1) + T(2) + ... + T(n-2) + (n-1)$

So we can subtract those equations and we get

$n*T(n) - (n-1)*T(n-1) = T(n-1) +1$

$n*T(n) = (n-1)*T(n-1) + T(n-1) +1$

$n*T(n) = n*T(n-1) + 1$

$T(n) = T(n-1) + 1/n$

And "unrolling" this equation, we have:

$T(n) = 1 + 1/2 + 1/3 + ... + 1/n$

And the right side of the equation is the nth harmonic number. We can show that the nth harmonic number is $\Theta(\log n)$ So we have that the average time for the algorithm is $\Theta(\log n)$

Answer 2

Best Case time complexity is when you randomly choose an element and it comes out to be the desired element. In this case, time complexity is constant, i.e., O(1)

Worse case is when the very first or last element gets selected randomly every time and the desired element lies at the end or beginning of the array, respectively! For example, consider the array {9,8,6,4,5}. Suppose we need to find 5. Worse case scenerio is: 9 is selected randomly. We consider the right array. 8 is selected now. again we consider the right array. 6 is selected next, so on and so forth until we reach 5. Here, we have traversed through every element of the array so the complexity will be O(n).