# Average case of simple algorithm like binary search

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?

• 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. Commented Aug 7, 2018 at 8:06
• 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. Commented Aug 9, 2018 at 8:10

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.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}