I needed help figuring out the correct calculation of the growth order of this code excerpt (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 had doubts. And then it will be necessary to add all growth orders in order to get the final solution.
As you suspected, the second iteration affects the third iteration. Being more specific, for all j between [1, N] , the third iteration will be repeated around N/k times. Already the first iteration is completely independent and independent of that.
Focusing on the two most external iterations, for each i , they will be executed the following number of times:
This,then,isNtimesapartofa harmonic series . As it has been reported that% of%, then the sum of the harmonic series up to N= 2^M will give N (proof in article linked ). Applying the above formula, we then have 1+M/2 .
Since the first formula is independent, it will% re% of that order of magnitude, so it will run in% with_%. Since we are in notation Big-O , and as O(N(1 + M/2)) , then the order of growth atomatic function is N