# The average time complexity of linear search with weighted probability

Given array of numbers $$A[1..n]$$. We search for element $$x$$ with linear search. Also we know that, element $$x$$ occurs in $$A$$ and probability of $$x$$ be in second half of the array is $$3$$ times of probability $$x$$ be in first half. What is the time complexity of linear search in average case?

Because of $$x$$ is in $$A$$, let $$p$$ be probability $$x$$ be in first half, so $$p+3p=1$$ so $$p=\frac{1}{4}.$$

Also I define Random variable $$X$$ as follow:

$$X_i = \begin{cases} \frac{1}{4}& ,1\leq i\leq \frac{n}{2} \\ \frac{3}{4}& ,\frac{n}{2} Let $$X=X_1+X_2+\dots+X_n.$$ Now the expected of $$X$$ is as follow

$$E[X]=\frac{1}{2n}\sum_{i=1}^{\frac{n}{2}}X_i+\frac{3}{2n}\sum_{i=\frac{n}{2}+1}^{n} X_i$$ After solving above equality, $$E[X]=\frac{10n+8}{16}$$. But I think the answer is $$\frac{5n}{8}$$. What is my wrong?

• Random variable defined with brace has only 2 different value, while in sum below it has $n$ different values. Commented May 21, 2022 at 14:08
• @zkutch How I can fix it? Commented May 21, 2022 at 14:10
• Write down separately values and probabilities for $X$. What you wrote are probabilities only. Commented May 21, 2022 at 14:11
• @zkutch I fix it. Are you agree? Commented May 21, 2022 at 14:22
• You need to write only values for random variable, not values times probabilities. This last is used in formula for expected value. Commented May 21, 2022 at 14:58

We must assume $$n$$ even. As the average of an arithmetic progression is the average of the extreme members, the number of comparisons for the first half is $$\dfrac{n+2}4$$, and that for the second half is $$\dfrac{3n+2}4$$.

Then taking the weighted sum,

$$\dfrac{5n+4}8.$$

Anyway, we can spare the very last comparison because we know that the element is in the array and we must deduct $$\dfrac3{4n}$$.

• Can you explain more about your idea? Thank you. Commented May 21, 2022 at 15:16
• @jhjhb: which "idea", this is just a computation ? What is unclear ?
– user16034
Commented May 21, 2022 at 15:17
• You are agree that my idea is correct? Commented May 21, 2022 at 15:19
• But the i have doubt about that the answer is $\frac{3n}{4}$ or $\frac{5n}{8}$. Commented May 21, 2022 at 15:20
• @jhjhb: IMO, neither. By the way, there is no $\frac{3n}4$.
– user16034
Commented May 21, 2022 at 16:12