Big O analysis for problem where number of items searched is unknown Consider this problem: you are searching an array of elements and are comparing the square of the current element to some number K. Essentially, you are looking to see if the square root of K is in the array. With this algorithm, chances are, you will not search the entire array because you will either find the square root or you will find that the square root is not in the array. 

As such, you are searching only a fraction of the array, which lets say has M elements. Does this mean that the big O is still O(M), even though you are not searching all of the elements?
Big-O gives the upper bound function of any analysis. For an algorithm you could represent all (Worst, Average, Best) cases in Big-O notation.

In your case,


Worst case: The required element is not present in the array (or is the last element of the array) : O(M)
Best case: The element is found in the first position itself: O(1)
Average case: Average of all possible case, i.e., the average time complexity of the cases where the element could be found at each possible position:


$$
\begin{align}
 = \frac{(1 + 2 + 3 + ... + M)}{M} \\
 = \frac{M(M + 1)/2}{M} \\
 = (M + 1)/2\\
= O(M)
\end{align}
$$

The average case is what you're looking for, which again O(M) only.