Algorithm Analysis question from Skiena's Algorithm Design Manual

user_14052379 0
Viewed 179

I am stuck on this question... enter image description herefrom Skiena's algorithm design manual.

This is part of the solutionenter image description here provided on his companion site.

I am unclear as to why adding 1 is necessary for the summation of k=j to i+j. I understand that the summation can further be broken down into the summation of k=1 to i+j minus the summation of k=1 to j, but I do not understand why 1 has to be added.

discrete-mathematics math algorithm
1 Answers

Let:

S is the sum of k from j to i+j.

We can break it as subtraction of summation i.e. s1(from k = 1 to k = i+j) and s2(from k = 1 to k = j-1).

s1 = i+j (summation from 1 up to i+j)

s2 = j-1 (summation from 1 up to j-1)

S = s1 - s2

S = (i+j) - (j-1)

S = i + j - j + 1

Hope you get it...

user_136519780
Related