Hi this is a question from an exam review. I have to find the running time(in Big-O) of the following code fragment.
sum = 0;
for( i = 0; i < n; i++ )
for( j = 0; j < i * i; j++ )
for ( k = 0; k < j; k++ )
++sum;
I think that it is O(n^4). The innermost loop executes to n, the second executes to n^2, and the outermost executes n times. Thank you all for your help
No, it is not O(4).
A better way to see this is to count how many times the loop executes(in fact, that is what the code is doing).
sum(sum(sum(1, k=0..j), j=0..i*i), i=0..n)
= sum(sum(j,j=0..i*i),i=0..n) = sum(i*i*(i*i+1)/2,i=0..n) which is on the order of sum(i^4, i=0..n) which is on the order of n^5.
Essentially because the middle loop is i*i and is being executed for each of the inner most loop it needs to be counted an extra time.
In C++
1 0
2 0
3 6
4 42
5 162
6 462
7 1092
8 2268
9 4284
10 7524
11 12474
12 19734
13 30030
14 44226
15 63336
16 88536
17 121176
18 162792
19 215118
You can use this table and compute the finite differences(taking derivatives) until the result is a constant or 0. You'll find that it takes 5 derivatives to have a constant list. This means that it the list is on the order of n^5.
e.g., If we had a list where each difference between two elements were a constant then the list could be represented by a linear function. If the difference of the difference was constant then it would be a quadradic, etc. (it doesn't matter about the lower order terms because they get translated by the derivative/difference)
Formally, using Sigma Notation would help to deduce the order of growth with sharp precision.
You can think simply:
In the first loop: i = n
second loop: j = i*i => j = n^2
third loop: k = j => k = n^2
So, the bigO = n * n^2 * n^2 = n^5
