sequential search analysis

Question

Hi All, I am reading algorithms in C++ by Robert Sedwick it was mentioned as follows

Sequential search in an ordered table examines N numbers for each search in the worst case and about N/2 numbers for each search on average.

            This result follows from assuming that the search is equally 

likely to terminate at any one of the N+1 intervals defined by the N numbers in th table which leads immediately to the expression (1+2+3+4+...+N+N)/N = (N+3)/2.

Can any one please help me in understand how we came to above expression i.e., how N+3 /2 is arrived.

Thanks in advance Venkata

Answer 1

Sum of the first N integers (1 + 2 + 3 + ... + N) = (N+1)N/2

The easy way to see this is write out the sum forwards and backwards:

1 + 2 + 3 + ... + (N-2) + (N-1) + N

N + (N-1) + (N-2) + ... + 3 + 2 + 1

and then sum corresponding terms:

(N+1) + (N+1) + (N+1) + ... + (N+1) = N(N+1)

divide by 2 to get result (N+1)N/2

Then, (1 + 2 + 3 + ... + N + N)/N = ((N+1)N/2 + N)/N = (N + 3)/2

Side Note: There is a story about the famous genius mathematician Karl Friedrich Gauss (1777-1855), when he was a boy. His schoolmaster gave the class the problem of adding up the numbers from 1 to 100, thinking it would keep them busy for some time. But Gauss found the sum 5050 after just a few minutes, using the above reasoning. Note: Gauss was a true genius but much of Gauss's life history was written by Gauss!

Answer 2

1 + 2 + ... + N + N = N(N+1)/2 + N = N((N+1)/2+1) = N(N + 3)/2