Algorithm Recurrence formula

Question

Hi All, I am reading Algorithms in C++ by Robert Sedgewick. Basic recurrences section it was mentioned as This recurrence arises for a recursive program that loops through the input to eliminate one item Cn = cn-1 + N, for N >=2 with C1 = 1.

Cn is about Nsquare/2. Evaluating the sum 1 + 2 +...+ N is elementary. in addition to this following statement is mentioned. " This result - twice the value sought - consists of N terms, each of which sums to N +1

I need help in understanding abouve statement what are N terms here and how each sums to N +1, aslo what does "twice the value sought" means.

Thanks for your help

Answer 1

I think he refers to this basic mathematical trick to calculate that sum. Although, it's difficult to conclude anything from such short passage you cited.

Let's assume N = 100. E.g., the sum is 1 + 2 + 3 + .. + 99 + 100.
Now, let's group pairs of elements with sum 101: 1 + 100, 2 + 99, 3 + 98, ..., 50 + 51. That gives us 50 (N/2) pairs with sum 101 (N + 1) in each: thus the overall sum is 50*101.

Anyway, could you provide a bit more context to that quote?

Answer 2

The recurrence formula means:

C1 = 1
C2 = C1 + 2 = 1 + 2 = 3
C3 = C2 + 3 = 3 + 3 = 6
C4 = C3 + 4 = 6 + 4 = 10
C5 = C4 + 5 = 10 + 5 = 15
etc.

But you can also write it directly: C5 = 1 + 2 + 3 + 4 + 5 = 15

And then use the old trick:

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

= (N+1) * N

From there we get : 1 + 2 + ... N = N * (N+1) / 2

For the anecdote, the above formula was found by the great mathematician Carl Friedrich Gauss, when he was at school.

From there we can deduce a recursive algorithm is O(N square) and that is probably what Robert Sedgewick is doing.