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$
9
$\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$
  • $\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$ – James Okpe George Jun 25 '18 at 13:34
  • 1
    $\begingroup$ @JamesOkpeGeorge See the edit, it always holds $\endgroup$ – caverac Jun 25 '18 at 13:40
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$
  • $\begingroup$ Thanks so much @InterstellarProbe, that was good $\endgroup$ – James Okpe George Jun 25 '18 at 13:57
  • $\begingroup$ Sadly I could not pick two response as answer $\endgroup$ – James Okpe George Jun 25 '18 at 14:05

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.