You are viewing a single comment's thread. Return to all comments →
A straight forward implementation would start with an array for and perform modifications, where the elements for
are getting the value added.
This would need
The above solution manages to requires setup steps and a final integration step visiting not more than array elements, so it is . For the constraints not more than about steps are needed, which is possible to compute with the given resources.
Let us start with the continuous case:
We start with a constant function and then add the modifications, going through a sequence of modified functions .
Given and adding the value for all times , this results into the modified function
For the discrete case this seems to turn into
So the modeling of the derivative is very efficient, only recording the changes at the interval
After modifications of the constant null function we get:
Finally is reconstructed by summing up (integrating) over :