From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

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