Order Growth

Asked

Viewed 181 times

2

Needed help to figure out the correct calculation of the order of growth of this code snippet (function of N=2 M)

int sum=0;
 for (int i = 0; i < = N; i++)
   for(j = 1; j <= N; j++)
     for(k = 1; k <= N; k=k+j)
       sum++;

The first two FOR cycles have growth order O(N) but in the case of the third FOR cycle I was left with doubts. And then it will be necessary to add up all the growth orders in order to get the final solution.

c

  • In the third loop, you will have O(floor(N/j)) steps for each j, so it will be the sum with j varying within [1,N]

1 answer

3


As you yourself suspected, the second iteration affects the third iteration. Being more specific, for all j amid [1, N], the third iteration will be repeated around N/j times. Already the first iteration is completely alien and independent to this.

Focusing on the two outermost iterations, for each i, they will be executed the following number of times:

somatório de N/k para k em <code>[1,N]</code>

That, then, is N times a part of a harmonic series. How was it reported that N= 2^M, then the sum of the harmonic series until N will give 1+M/2 (evidence in the linked article). Applying to the above formula, we then have O(N(1 + M/2)).

As the first formula is independent, it will N repetitions of that order of magnitude, therefore it will rotate in O(N*N(1 + M/2)). How we are in notation Big-O, and how M = lg N, then the order of growth asymptotic of function is O(N^2 * lg N)

Browser other questions tagged c

You are not signed in. Login or sign up in order to post.