0

Please refer to the code fragment below:

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

If one was to analyze the run-time of this fragment in Big-Oh Notation, what would be the most appropriate value? Would it be O(N^4)?

user7366442
  • 731
  • 2
  • 9
  • 16

3 Answers3

0

I have to say O(n^5). I maybe wrong. n is the length of the array in this question I am assuming. If you substitute it, i will stop when i < n j will stop when j < n*n and k will stop when k < n * n. Since these are nested for-loops, the run time is O(n^5)

0

I think it's O(n^5)

We know that

1 + 2 + 3 + ... + n = n(n+1) / 2 = O(n^2)

1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1) / 6 = O(n^3)

I think that similary statement is true for sum of bigger powers.

Let's think about these two lines

for( j = 0; j < i * i; j++ ) 
        for( k = 0; k < j; k++ )

This loop's time complexity for fixed i is 1 + 2 + ... + (i-1)^2 = (i-1)^2(1 + (i-1)^2) / 2 = O(i^4)

But in our code i changes from 0 to n-1, so we like add fourth powers, and as I said before

1^k + 2^k + ... + n^k = O(n^(k+1))

That's why time complexity is O(n^5)

moskalenco_a
  • 289
  • 1
  • 6
0

Given this code, consider each loop separately.

sum = 0;
for( i = 0; i < n; i++ )         //L1
    for( j = 0; j < i * i; j++ ) //L2
        for( k = 0; k < j; k++ ) //L3
            sum++;               //

Consider the outermost loop (L1) alone. Clearly this loop is O(n).

for( i = 0; i < n; i++ )         //L1
    L2(i);

Consider the next loop (L2). This one is harder, but the loop is O(n^2).
See this SO answer for why the loop is O(n^2): Big O, how do you calculate/approximate it?

    for( j = 0; j < i * i; j++ ) //L2
        L3(j);

Consider the next loop (L3). Since you know that the L2 loop is O(N^2), what is this loop? (leaving reader to complete their homework).

        for( k = 0; k < j; k++ ) //L3
            sum++;               //
ChuckCottrill
  • 4,360
  • 2
  • 24
  • 42