Figuring out the upper bound of an algorithm with multiple embedded for-loops

[vaderboi]

In my textbook, Data Structures and Algorithm Analysis in C++ (Fourth Edition) by Mark Allen Weiss, in the problems for chapter 2, "Algorithm Analysis", on pages 89 - 90, we are asked to evaluate several program fragments and analyze the upper bound of their run-time using big-Oh notation. In case anyone is unfamiliar with big-Oh, here is the definition that you can find at https://www.cs.sfu.ca/~ggbaker/zju/math/growth.html:

For functions f(x) and g(x), we will say that “f(x) is O(g(x))” [pronounced “f(x) is big-oh of g(x)”] if there are positive constants C and k such that
|f(x)|≤C|g(x)| for all x>k.

On page 90, of my textbook there is this pseudo-code fragment to evaluate:

 sum = 0;
       for( i = 0; i < n; ++ i )
       {
            for(j = 0; j < i * i; ++j )
            {
                for( k = 0; k < j; ++k )
                {
                     ++sum;
                }
            }
       }

Mind you, I am not just interested in finding out what this algorithm is big-Oh of, I would like to find as exact a value as possible.

Here is what I have attempted so far in my HW (also since it would take forever to do, please assume that any integer value after some function of N is an exponent. I apologize for how messy this looks):

The outer loop runs N time. The inner loop is dependent on the growth of i2. To figure out the time it takes for these loops run together I will need to use the summation formula.

a0 = 0 and a2 = (N – 1)2 - 1 because the last element will not be multiplied by itself, only the second to last. The total value is subtracted by 1 because 0 and 1 are skipped. ( N(0 + (N – 1)2 – 1) )/ 2 = N ( N2 – 2N ) / 2 = N3 – 2N2 / 2

The last for-loop runs in relation to j. Once again we need to do a summation notation to figure out what the final loop does. We know that since k < j the inner for loop is essentially run j * j times or j2 times.

So a0 = 0 and afj = N3 – 2N3 / 2. The N value outside is (N3 – 2N2 / 2) because that is the number of times the loop will be run. (N3 – 2N2 / 2) ((N3 – 2N2 / 2) / 2)) = (1/2) N3 – N2 ( (1/8)N3 – (1/4) N2) = (1/16) N6 – (1/8) N5 – (1/8) N5 + (1/4) N4 = ( N6 + 4N4 / 16 )

So in total the algorithm will be an element of O(N6).

So is my reasoning correct that the algorithm is an element of O(N^6) and has an upper bound of (N^6 + 4N^4) / 16? Or am I missing something here?

[lastchance]

I made it O(n⁵), actually. Did you find out the actual answer?

[vaderboi]

I don't know what it is. My teacher won't grade stuff until the end of the week. How did you arrive at O(n^5)?

[lastchance]

Any advances on ...

sum = n(2n4-5n3+5n-2)/20

EDIT. That factorises!

sum = n(n-1)(n+1)(n-2)(2n-1)/20

Definitely O(n⁵)


You can try it out:

#include <iostream>
using namespace std;

int f( int n )   // Formula
{
   int n2 = n * n, n3 = n2 * n, n4 = n3 * n;
   return n * ( 2 * n4 - 5 * n3 + 5 * n - 2 ) / 20;
   // return n * (n - 1) * (n + 1) * (n - 2) * (2 * n - 1) / 20;  // Alternative
}


int g( int n )   // Triple loops
{
   int sum = 0;
   for ( int i = 0; i < n; ++ i )
   {
      for ( int j = 0; j < i * i; ++j )
      {
         for ( int k = 0; k < j; ++k )
         {
            ++sum;
         }
      }
   }
   return sum;
}


int main()
{
   for ( int n = 2; n <= 10; n++ ) cout << n << "  " << f(n) << "  " << g( n ) << '\n';
}

2  0  0
3  6  6
4  42  42
5  162  162
6  462  462
7  1092  1092
8  2268  2268
9  4284  4284
10  7524  7524

You might find the following link a help:
http://mathworld.wolfram.com/PowerSum.html

[vaderboi]

I understand how summations work. I think I just got some of the algebra wrong if indeed the formula is an element of O(n^5) (which it very well could be).

[vaderboi]

I will take another look at it and see where I may have made an error.

[vaderboi]

Do you know where I may have made a mistake? It probably would be somewhere around finding the summation value for the most inner loop.

[doug4]

Mind you, I am not just interested in finding out what this algorithm is big-Oh of, I would like to find as exact a value as possible.

Generally you don't need an exact value. The big-O notation is used to categorize algorithms to determine which is better as a data set is scaled.

Lets' say you have algorithm A1 with O(n + K) and algorithm A2 with O(n^2). The constant K is so large for A1 that A2 is actually 3 times faster than A1 when working with a data set of 25 elements.

Now lets scale the algorithm up to 2500000 elements. The n^2 term in A2's algorithm is so much larger than the K in A1 that now A2 takes hours longer than A1.

For this reason, big-O notation generally ignores terms beyond the largest exponent. It shows the factor of what rate the time grows as data increases.

Plotting time against data size would be linear for an A1. It would be parabolic for A2. It would be cubic for an algorithm of O(n^3).

In your case:

The outer loop runs N times.

The middle loop runs from 1 up to N^2. Not every iteration runs N^2 times, but the growth of the middle loop is square.

The inner loop would also run from 1 up to N^2. Again, not every iteration run N^2 times, but the growth of the inner loop is square.

The big-O of the overall algorithm is N * N^2 * N^2: O(n^5).

Edit: added the missing exponent.

[vaderboi]

But doesn't the inner loop run O(N^3) time multiplied by O(N^3)? The middle loop runs O(N^3). I think I am with you both on that. But the most inner loop would run i^4 number of times, right? Say i = 2. j will iterate 4 times and the most inner loop will run 16 times.

How is my math wrong here?

So a0 = 0 and afj = N3 – 2N3 / 2. The N value outside is (N3 – 2N2 / 2) because that is the number of times the loop will be run. (N3 – 2N2 / 2) ((N3 – 2N2 / 2) / 2)) = (1/2) N3 – N2 ( (1/8)N3 – (1/4) N2) = (1/16) N6 – (1/8) N5 – (1/8) N5 + (1/4) N4 = ( N6 + 4N4 / 16 )

[vaderboi]

I know that the lower order terms and constants are irrelevant in terms of assessing whether a function is an element of some big-Oh value. I just want to know if my algebra and thinking is flawed.

[Ganado]

doug4, did you mean to say N * N^2 * N^2?

[lastchance]

The inner loop runs j times as j goes from 1 to (just under) i^2. So for each i you are summing O(i^2) numbers, each of which is O(i^2). Thus j and k loops together are O(i^4). But then i is O(n) so you sum O(n) groups of O(n^4) numbers; i.e. O(n^5).

The exact answer requires you to think very carefully about exactly which loops run (it's not that obvious), the sum-of-powers formulae in the link I gave, and a horrendous lot of algebra.

[mbozzi]

The sum you want to work with is (in LaTeX)

\sum_{1\leq i\leq n}{\sum_{1\leq j\leq i^2}j} =
\frac{1}{2}\sum_{1\leq i\leq n}{(i^4 + i^2)} =
\frac{1}{2}\sum_{1\leq i\leq n}{i^4} + \frac{1}{2}\sum_{1\leq i\leq n}{i^2}

It's apparent that's O(n^5) is an upper bound.

The sum of fourth powers can be evaluated with Faulhaber's formula, if you really want to. The resulting polynomial has degree 5, though, and that's really all you need to know.
https://en.wikipedia.org/wiki/Faulhaber%27s_formula

[vaderboi]

So I tried doing the summation formula starting from the inner most loop and I wanted to know what you all thought of my work and the result:

To figure out the time complexity of this algorithm, I find it is best to start with a summation formula on the inner most loop.

It will run N – 1 (because the iterator never makes it to 10) multiplied by 4 + N2 – 2N + 5 all divided by 2.

( (N – 1) (N2 – 2N + 9) ) / 2 = (N3 – 3N2 + 11N – 9) / 2

So far the algorithm is an element of O(N3). Now we input this value in to another summation formula that represents how many times the middle function is called. The value will be added together N – 2 times. The outermost loop also runs N – 2 times.

( ( (N – 1) ( ( ((2)3 – 3(2)2 + 11(2)2 – 9)/ 2 ) + ( ( (N – 1)3 – 3(N – 1)2 + 11(N – 1) – 9 ) / 2 ) ) / 2
We know the first value of N is 2 so it is input in to the value we found in the last summation algorithm. We also input (N – 1) in to another copy of it because that represents the final iteration.

(N – 1) ( 1/2(N3) – N2 + 10N – 12 + 31/ 4 ) / 2

(½(N4) – (1/2)N3 + 10N2 – 12N + (31/4)N) / 2

1/4(N4) – ¼(N3) + 5N2 – 6N + (31/8)N

And then finally we input this value for the final summation formula which is performed by the outermost loop.

( (N – 1) ( (¼(2)4 – ¼(2)3 + 5(2)2 – 6(2) + (31 / 8) (2)) / 2) + ((1/4(N - 1)4 – ¼(N - 1)3 + 5(N – 1)2 – 6(N – 1) + (31/8) (N – 1) ) / 2 ) ) ) / 2

( (N - 1)( ( (10 + 31/4 ) / 2 ) + ( ( ¼(N4 – 4N3 + 6N2 – 4N + 1) – ¼(N3 – 3N2 + 3N – 1) + 5(N2 – 2N + 1) – 6N +(31/8)N + 6 – 31/8 ) / 2 ) / 2

( (N – 10) ( 1/8(N4) – 3/8(N3) + 7N2 – 7/2(N) + (31/16)(N) + 8 – 93/16 ) ) / 2

(1/8(N5) – 9/8(N4) + (7 – 30/8)N3 + 63(N2) + (31/16 + 70/2)(N2) + 8N – 93/16(N) + 80 + 930/16) / 2

1/16(N5) – 9/16(N4) + (19/16)(N3) + (1599/32)(N2) + 4N – 35/32(N) + 1871/32

[salem c]

Big-O doesn't care about the minor terms.

This is an asymptotic limit, so N⁵ will always completely dominate any values of N⁴ N³ etc.

[vaderboi]

I know that. I just wanted to know if my algebra was solid and if I understand how to correctly employ sum notation.

[lastchance]

@vaderboi.
No your algebra isn't solid. It was wrong from the first line:

It will run N – 1 (because the iterator never makes it to 10) multiplied by 4 + N2 – 2N + 5 all divided by 2.

None of which makes any sense.

As others have told you, it is the primary order, in this case O(N⁵) which is important for choice of algorithm.

However, if you absolutely want to see the summation then here's my take on it. Excuse my scrawly handwriting.
https://imgur.com/eyKjLPO



You need the sum of the 2nd and 4th powers of natural numbers (see http://mathworld.wolfram.com/PowerSum.html ) and you can test the formula with my earlier code:
http://www.cplusplus.com/forum/general/264015/#msg1138279

[doug4]

doug4, did you mean to say N * N^2 * N^2?

Thanks, @Ganado. I corrected it.

[vaderboi]

Yeah. Figuring out how to calculate nested sums is a little outside of my skillset right now. The algebra was way too intensely crazy for me right now. So I will be content with it more generally for now. Lol.

[vaderboi]

Thank you all for your responses. Figuring out what big-Oh set the algorithm belongs to isn't that hard. I just wanted to understand the algebra. But it really doesn't matter right now.