Big O notation for Average case in Linear search
Let us recall the definition of big-O notation.
If a function g(n) = O(f(n)), this implies that there exists two positive constants n0 and c, such that for all n &gt; n0, 0 ≤ g(n) ≤ c f(n)
Hence, it follows that O(n) is equivalent to O(n/2), as n is just n/2 multiplied by a constant factor, which in this case is 2.