The 'derivative' of a sequence. (2 Viewers)

[seanieg89]

 

[seanieg89]

bump.

 

[GoldyOrNugget]

Does this 'sequence derivative' have a proper term? It comes up all the time in informatics. I've always called it the 'delta array' for lack of a better term. And there's also its 'integral' equivalent, which we call the cumulative array, where the nth term is the sum of terms 0..n. That one has the nice property that you can construct it in linear time with

cum[0] = arr[0]
for i = 1 to n
  cum[i] = arr[i] + cum[i-1]

and then perform range sum queries in constant time; the sum of elements i..j can be found with a single operation, cum[j] - cum[i-1] (or just cum[j] if i == 0)

 

[braintic]

Would a moderator please move this thread elsewhere. It is not high school maths.

 

[lolcakes52]

Would a moderator please move this thread elsewhere. It is not high school maths.

So you know the solution and it is above the 4 unit level?

 

[seanieg89]

Would a moderator please move this thread elsewhere. It is not high school maths.

The induction question is very much high school maths. The exploration at the end is only for people who want to look at it further.

 

[seanieg89]

Does this 'sequence derivative' have a proper term? It comes up all the time in informatics. I've always called it the 'delta array' for lack of a better term. And there's also its 'integral' equivalent, which we call the cumulative array, where the nth term is the sum of terms 0..n. That one has the nice property that you can construct it in linear time with

cum[0] = arr[0]
for i = 1 to n
  cum[i] = arr[i] + cum[i-1]

and then perform range sum queries in constant time; the sum of elements i..j can be found with a single operation, cum[j] - cum[i-1] (or just cum[j] if i == 0)

Probably, I have not done much informatics. It is a pretty natural construction to make, (as is the summatory analogue).