This loop can be expressed as the sum:
Reducing this, sum by sum from the rhs:
n=1 gives zero;
and order is O((n^3)/3)
Alternative Derivation
Taking the following well-known formula for the sum of the integers
to
:-
And noting that:-
We continue our derivation thus:-
Given our formula for the sum of integers, substituting
for
gives us:-
Thus continuing with our derivation:-
Let us consider the well-known formula for the sum of the squares of the integers between
and
:-
As before, let us substitute
for
:-
Substituting this into our derivation gives us:-
Thus the solution is
. This is the equivalent to the solution given by the previous derivation.
The Big-Oh complexity of this function (ignoring constants) is O(n^3), as the RAM model dictates that each iteration of the increment of
is a time-step. We can ignore the first and last line's contribution to running time for the purposes of Big-Oh, as they do not contribute to the growth of the time taken with input size.
Return to Chapter 2