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