7
$\begingroup$

I have the formula for finding the average time of an linear search algorithm as below

\begin{equation*} AT\ =\frac{\ \sum ^{n+1}_{i\ =\ 1} \ \theta ( i)}{n+1}. \end{equation*}

The above formula was simplified to become the one below, I am not sure how it was moved from that to this. Any help? \begin{equation*} AT\ =\ \frac{\theta (( n\ +\ 1) \ \times \ ( n\ +\ 2) \div 2)}{n\ +\ 1}. \end{equation*}

$\endgroup$
0
13
$\begingroup$

A linear operator satisfies the following property:

$$\theta(a)+\theta(b) = \theta(a+b)$$

This means that:

$$\sum_{i=1}^{n+1}\theta(i) = \theta\left( \sum_{i=1}^{n+1} i \right)$$

caverac answered about that summation yielding $\dfrac{(n+1)(n+2)}{2} = \dbinom{n+2}{2}$.

$\endgroup$
2
  • $\begingroup$ Thanks so much @InterstellarProbe, that was good $\endgroup$ Jun 25 '18 at 13:57
  • $\begingroup$ Sadly I could not pick two response as answer $\endgroup$ Jun 25 '18 at 14:05
10
$\begingroup$

You can follow this link for a detailed explanation, but in short

$$ 1 + 2 + \cdots + k = \frac{k(k + 1)}{2} $$

In your case $k = n + 1$


EIDT

Proof:

Call $S = 1 + 2 + \cdots + (k - 1) + k $, note that you can also write it in reverse order $S = k + (k - 1) + \cdots + 2 + 1 $, so that

\begin{array}{} S &=& 1 &+& 2 &+\cdots+& (k-1) &+& k\\ S &=& k &+& (k-1) &+\cdots+& 2 &+& 1\\ \hline 2S &=& (k+1) &+& (k+1) &+\cdots+& (k+1) &+& (k+1) \end{array}

So you have

$$ 2S = k (k + 1) $$

$\endgroup$
2
  • $\begingroup$ Thanks for this, I am still reading the wiki page, but just to verify, if that is a formula that is always through, how do I prove to someone that doing that summation will always give k(k+1)/2 $\endgroup$ Jun 25 '18 at 13:34
  • 1
    $\begingroup$ @JamesOkpeGeorge See the edit, it always holds $\endgroup$
    – caverac
    Jun 25 '18 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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