# 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

• Please add the definition or informal description that you are working from of what $f \in O(g)$ means. (Give it some thought, too.) Aug 27, 2020 at 7:24
• Your conclusion "therefore..." is wrong.
– user16034
Aug 27, 2020 at 21:50
• Are you assuming that the elements of your list are random and that the element doing the lookup is random? In real life that is often not the case. If the list is sorted and you always search for the first element you will average 1 comparison per lookup. Oct 7, 2020 at 17:21

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 > 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.

• That means O(4)=O(2)? Does both give same answer??? Can you give me an example for that please??? Oct 6, 2020 at 6:19
• Yes. O(1000) = O(4) = O(2) = O(1), and O(n/2) = O(n), but for example O(n^2) is not O(n), since there aren't any constants c, n0 such that n^2 < c*n for all n>n0. Oct 6, 2020 at 11:01

Let the probability that the key is found be $$p$$. Then

• in case of a miss (probability $$1-p$$), we perform $$n$$ comparisons,
• in case of a hit (probability $$p$$), we perform from $$1$$ to $$n$$ comparisons with equal probability.

Hence the expected number of comparisons is

$$(1-p)n+\frac{n+1}2p=\frac{(2-p)n+p}2.$$

In Landau's asymptotic notation, this is $$\Theta(n)$$.

• That means O(4)=O(2)? Does both give same answer??? Can you give me an example for that please??? Oct 6, 2020 at 6:19
• @SanmithaSadhishkumar: it is high time that you reviewed the definition of O.
– user16034
Oct 6, 2020 at 6:50

So most of the time we generally disregard constants in complexity analysis, and hence we say that the base doesn't matter. Always remember, whenever we are going for any kind of asymptotic notation we must consider the highest value of 'n'. Big-oh (i.e., $$\mathcal{O}$$) does not deal with the constant factor (i.e, here it is $$\frac{1}{2}$$). The constant factor associated with 'n' changes the slope of the curve only. However, $$\mathcal{O}$$ notation does not deal with this slope of the curve, it deals only with the shape/nature of the curve. This is why $$\mathcal{O}(\frac{n}{2})\equiv \mathcal{O} (n)$$ . Please give an upvote to my answer if you satisfy with this. Thank you.

*** Newly Inserted**

Big-oh notation defines the upper boundary of the function. It does not deal with the slope of the function, it works only the shape of the curve. For example suppose, $$Y=mx+c$$, is a straight line equation, now for any value of $$m$$ it will be a straight line, for different value of $$m$$ we will get the only different slope. But, Big-oh doest not deal with the slope of the function. meanwhile, we must remember that growth of the function concept while addressing the Big-oh. this is an asymptotic notation to express the time complexity. For more details please follow the book "Introduction to Algorithms", written by Thomas H. Coreman, please see the Chapter "Growth of the functions".

• That means O(4)=O(2)? Does both give same answer??? Can you give me an example for that please??? Oct 6, 2020 at 6:19
• yes madam. The answer will be the same. Actually $\mathcal{O}(2)$ is a constant term which is also similar to $\mathcal{O}(1)$. Oct 6, 2020 at 6:21

My 2 cents (Please, accept my apologies, native English speakers - I will be grateful for stylistic corrections).

Firstly let me say, that when pointing minimum (best case) and maximum number (worst case) of comparisons as $$1$$ and $$n$$ and using "therefore" average is $$\frac{n+1}{2}$$ leaves impression, that you calculate arithmetical mean, which is wrong action.

Based on above, firstly, I introduce conception of average case: suppose we are considering some algorithm and define $$T$$ its running time or time complexity function as number of some particular operations, depending on input with size $$n$$. Suppose $$T$$ can obtain only finite amount of values $$x_1,x_2,\cdots,x_k$$ and for each value we know also its expectation i.e. we have numbers $$p_1,p_2,\cdots,p_k$$, where each $$p_i$$ characterizing expectation for $$T$$ to take value $$x_i$$. Not going deeply in soul of term "expectation", on first step, we can simply understand them as numbers with properties $$\forall i,0 \leqslant p_i \leqslant 1$$ and $$\sum\limits_{i=1}^{k}p_i=1$$ i.e shares, parts of unit. Now average case we define as: $$AT=\sum\limits_{i=1}^{k}p_ix_i$$

In most simple case we can consider equal expectations i.e. $$\forall i, p_i=\frac{1}{k}$$ and call it uniform expectation. Not uniform expectations, sometimes, are, also, very useful and interesting.

Now coming back to linear search algorithm, let's assume, that we have array with length $$n$$ and we are searching for some particular value. Usually we consider $$T$$ as number of comparisons happened during searching. Obviously we have $$n$$ possible cases to find searched value respectively on places $$1,2,\cdots,n$$ or not find it at all, so we have $$n+1$$ possible cases altogether. Obviously $$T$$ get value $$i$$ if find happens on place $$i$$ and together with case to find happened on $$n$$-th $$T$$ get value $$n$$ also in case when search failed. So we have for $$T$$ $$\begin{cases} \ \ 1\quad 2 \quad\cdots \quad n \quad n & \text{ values}\\ \ \frac{1}{n+1}\ \frac{1}{n+1} \cdots \ \frac{1}{n+1} \ \frac{1}{n+1} & \text{ expectations} \end{cases}$$ Now average case is $$AT=\sum\limits_{i=1}^{n}\frac{i}{n+1}+\frac{n}{n+1}=\frac{1}{n+1}\frac{n(n+1)}{2}+\frac{n}{n+1}=\frac{n}{2}+\frac{n}{n+1}$$ Now come time to remember definition of big-$$O$$ $$O(f)=\{g: \exists C>0, \exists N \in \mathbb{N}, \forall n>N, g(n) \leqslant Cf(n)\}$$ and we can conclude $$AT=\frac{n}{2}+O(1)=O\left(\frac{n}{2}\right)=O(n)$$ And now we come to your last question and let me show, that $$O\left(\frac{n}{2}\right)=O(n)$$ i.e. $$O\left(\frac{n}{2}\right) \subset O(n)$$ and $$O(n) \subset O\left(\frac{n}{2}\right)$$:

1. Suppose $$f \in O\left(\frac{n}{2}\right)$$, which means $$\exists C,N$$ such that $$f(n) \leqslant C\frac{n}{2}=\frac{C}{2}n=C_1 n$$, so $$f \in O(n)$$.
2. Suppose $$f \in O(n)$$. This means $$\exists C,N$$ such that $$f(n) \leqslant C n=2C \frac{n}{2} = C_1 \frac{n}{2}$$ , so $$f \in O\left(\frac{n}{2}\right)$$.

Gift 1. This gift I would recommend read after understanding above fully. Now let's consider not uniform case, so lets assume that we expect to find searched value with expectation $$p$$, i.e. find it in any place from $$1$$ to $$n$$, and, so, not to find it with expectation $$1-p$$. Now we have for for $$T$$ $$\begin{cases} \ \ 1\quad 2 \quad\cdots \quad n \quad n & \text{ values} \\ \ \frac{p}{n}\quad \frac{p}{n}\quad \cdots \ \ \frac{p}{n} \quad \ 1-p & \text{ expectations} \end{cases}$$ Now average will be: $$AT=\sum\limits_{i=1}^{n}\frac{ip}{n}+n(1-p)=\frac{p}{n}\frac{n(n+1)}{2}+n(1-p)=n\left(1- \frac{p}{2}\right)+\frac{p}{2} = O(n)$$

Gift 2. There can be considered linear search algorithm, which counts 2 comparisons on each step, based on counts as a comparison with the desired value, so a comparison when the end of the cycle is checked. In this case is very interesting so called sentinel method of searching. The average of this algorithm is half of the considered classical search. An interesting exercise to test your awareness of the issue.

Review the definition of O(n). The average runtime is:

• $$f(x) = O(n) = O(0.5n)$$ average time or as sometimes written, $$f(x) \in O(n)$$. By definition this means, there is some number k so that $$\lim_{x\to\infty} \frac{f(x)}{n}\leq{k}$$
• $$f(x) = \Theta(n) = \Theta(0.5n)$$ average time or as sometimes written, $$f(x) \in \Theta(n)$$. By definition this means, there is some number k so that $$\lim_{x\to\infty}\frac{f(x)}{n}=k$$
• $$f(x) {\sim} 0.5n$$ average time. By definition this means, $$\lim_{x\to\infty} \frac{f(x)}{n}=1$$
• Welcome to COMPUTER SCIENCE @SE. Umm, you labelled average time for $O$ as well as for $\Theta$. Please provide a reference for the definitions you suggest to review/use. Oct 9, 2020 at 6:27
• I say "O(n) average time"--it's a whole phrase, not that O(n) always means average time. O(n) is a general notation used to describe any function from integers to integers and its asymptotic behavior. A google search suggest the definitions I was taught may be those from "Family of Bachmann–Landau notations" en.wikipedia.org/wiki/Big_O_notation Oct 9, 2020 at 10:53