Big O notation for Average case in Linear search Average case complexity for linear search is (n+1)/2 i.e, half the size of input n.
The average case efficiency of an algorithm can be obtained by finding the average number of comparisons as given below:
Minimum number of comparisons = 1
Maximum number of comparisons = n
If the element not found then maximum number of comparison = n
Therefore, average number of comparisons = (n + 1)/2
Hence the average case efficiency will be expressed as O (n).(I've seen this in many websites...)
Here, how can we say it as O(n) in big O notation or terminology. It should be O(n/2), I suppose. Kindly clarify me
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.