Difference between revisions of "2.1"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
(Created page with " This loop can be expressed as the sum: <math> \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\sum_{k=1}^{j}1 </math> Reducing this, sum by sum from the rhs: <math> \begin{align} &\sum_{i...")
 
(No difference)

Latest revision as of 19:25, 8 September 2020

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