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)
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