Finding a loop invariant in a program to compute sums of cubes?

Question

I'm not 100% sure what the invariant in a triple power summation is.

Note: n is always a non-negative value.

Pseudocode:

triplePower(n)
    i=0
    tot=0
    while i <= n LI1
        j = 0
        while j < i LI2
            k = 0
            while k < i LI3
                tot = tot + i
                k++
            j++
        i++

I know its messy and could be done in a much easier way, but this is what I am expected to do (mainly for algorithm analysis practice).

I am to come up with three loop invariants; LI1, LI2, and LI3.
I'm thinking that for LI1 the invariant has something to do with tot=(i^2(i+1)^2)/4 (the equation for a sum a cubes from 0 to i)
I don't know what to do for LI2 or LI3 though. The loop at LI2 make i^3 and LI3 makes i^2, but I'm not totally sure how to define them as loop invariants.

Would the invariants be easier to define if I had 3 separate total variables in each of the while loop bodies?

Thanks for any help you can give.

Also is the order of growth of this function: Θ(n^3)?

Answer 1

Your algorithm can be simplified like this (I hope you're accustomed to C Language syntax):

tot = 0;
for ( i = 0 ; i <= n ; i ++ )
    for ( j = 0 ; j < i ; j ++ )
        for ( k = 0 ; k < i ; k ++ )
            tot = tot + i;

And then, you can translate it into Sigma Notation:

Answer 2

When faced with a loop like this that computes a sum up incrementally, a good invariant to look for is whether the total sum you've computed so far is equal to the first part of the sum that you think it is. In this case, you want to compute the sum of the first n positive perfect cubes, and do so by adding in cubes one at a time. Thus one possible invariant would be that

tot = sum (j goes from 0 to i) j³

Additionally, what's the relation between i and n? Well, we should probably have that i ≤ n + 1. Why the n + 1? That's because on the last iteration, when i = n, we still increment i anyway. Using these two invariants, you can prove that this loop computes the correct value.

As for the runtime, you can compute this quite easily. First, how much work is being done on each iteration? O(1)? O(n)? O(n²)? Then, how many loop iterations are there? O(1)? O(n)? O(n²)? The product of these two terms will give you your answer.

Hope this helps!