7

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*}

Klangen
  • 5,075
George
  • 187

2 Answers2

13

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

SlipEternal
  • 10,555
  • 1
  • 17
  • 38
10

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) $$

caverac
  • 19,345
  • 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 – George Jun 25 '18 at 13:34
  • 1
    @JamesOkpeGeorge See the edit, it always holds – caverac Jun 25 '18 at 13:40