Average case of simple algorithm like binary search

Question

These questions is about one of my research. As I am not a computer scientist, formal answering is difficult to me.

I have a special search algorithm which the explanation here will take a lot of time. However I can explain it shortly by some notations.

Assume that we have an array of somethings (in my real research they are some cities which they form a path graph) with length $n$. First, we should select one element by some rules( I ignore the rules here) with $O(1)$ time. indeed, according to the rules this element is nearer element to my solution. However, as this rule does not follow a particular order, we can assume that the selection is random.

This element may take tree label, say $L,ドル $R$ and $M$. The label can be found in $O(1)$ time. If the label is $M,ドル then we found the solution. Else, if the label is $l,ドル then we found that this element is not solution and also all elements before it can not be a solution. similarly, this scenario is also correct when the label is $R,ドル i.e. this element is not solution and also all elements after it can not be a solution. This leads a binary like search algorithm with the difference that the first element is not the median of array. we can summarize the above statements as the following algorithm.

Input: An array $A$ with length $n$.
while length(A) > 1 do
 1. choose an element $k$ (for example, randomly with uniform 
 distribution) with $O(1)$. Find its label with $O(1)$.
 2.If the label is $M,ドル then stop
 3. else if the label is $l$ then delete $k$ and all elements before $k$.
 4. else if the label is $r$ then delete $k$ and all elements after $k$. 
end while

I know that the worst case complexity is $O(n^2)$ and the best complexity is $O(1)$. What is the average complexity?

• A.R.S: Assume the selected element is in place $i,ドル then $T(n)= T(n-i) + O(1)$. This leads the recursive function $T(n)=\frac{n-1}{n} T(n-1) + \frac{2}{n}.$ However this function has the wrong solution.
• Bulat: It's exactly how partition() algorithm in QuickSort works. Probably you can find its deep complexity analysis in textbooks such as Knuth TAOCP, Cormen Algorithms and so on.

Answer 1

The average case time complexity is $O(\log n)$ (with a suitable implementation). Intuitively, each iteration typically removes a constant factor of the elements from the array.

Here's a more formal analysis. Consider an iteration to be "good" if it removes at least 1ドル/3$ of the elements of the array. Then an iteration is good with probability 2ドル/3$. Let $X_1$ denote the number of iterations until the first good iteration; this is a geometric random variable, so its expected value is 1ドル.5$. Let $X_2$ denote the number of iterations after the first good iteration, until the second good iteration. Again, the expected value of $X_2$ is 1ドル.5$. And so on. Now note that after $j$ good iterations, only a $(2/3)^j$ fraction of elements remain, so after at most $k = \lg_{2/3} n$ good iterations, the array will have only a single element and will terminate immediately. The total number of iterations is $X_1 + X_2 + X_3 + \cdots + X_k$. By linearity of expectation, the expected value of this sum is 1ドル.5k$. Thus the expected number of iterations until this terminates is 1ドル.5 \lg_{2/3} n = \frac{1.5}{\log(2/3)} \log n = O(\log n)$.

You can implement this so each iteration takes $O(1)$ time. In particular, you don't actually remove elements in steps 3 and 4; you just keep track of the range of indices of non-removed elements. That's always a consecutive range, so everything is easy.

In this way, the algorithm takes $O(\log n)$ iterations on average, and $O(1)$ time per iteration, for an average-case running time of $O(\log n)$.

Incidentally, with this implementation, the worst case running time is $O(n)$ rather than $O(\log n)$. Each iteration of the loop removes at least one element from the array, so there can be at most $n$ iterations of the loop, and each iteration runs in $O(1)$ time, for a total of $O(n)$ worst-case running time.