0
$\begingroup$

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}<i\leq n \end{cases} $$ 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?

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

1 Answer 1

1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.