Can anyone explain what the time complexity is for this algorithm?
for (i = 1; i <= n; i++){
for(j = 1; j <= n; j += i) { // note: not j++
printf("Iteration %d : %d\n", i, j);
}
}
2 Answers
The printf in the inner loop is called exactly ceil(n) + ceil(n/2) + ceil(n/3) + ... ceil(n/n) times. To get rid of ceil, we know that ceil(y/n) is bounded above by y/n + 1, so we know that the number of executions is >= n + n/2 + n/3 ... n/n but is < n + 1 + n/2 + 1 + n/3 + 1 + n/4 + 1... + n/n + 1. The former can be factored to n(1 + 1/2 + 1/3 + 1/4 ... 1/n) and the latter can be refactored into to n(1 + 1/2 + 1/3 + 1/4 ... 1/n) + n.
The latter factor is of the first addend to infinity is the the harmonic series, which diverges. The sum of the first k terms from the Wikipedia page is known to be bounded:
which means that 1 + 1/2 + 1/3 + 1/4 ... 1/n is Ө(ln n) = Ө(log n); we can give strict bounds for the number of times that printf is called (c(n): n log n <= c(n) < n log n + 2n. Since n log n grows faster than 2n, we can keep only the former and notice that both bounds belong to Ө(n log n) and hence c(n) belongs to Ө(n log n) as well (Ө(F) means that the function is both Ω(F) and O(F)).
Comments
Another way to analyze the complexity is to investigate how many more iterations are added if you double n.
for (i = 1; i <= 2*n; i++){
for(j = 1; j <= 2*n; j += i) { // note: not j++
printf("Iteration %d : %d\n", i, j);
}
}
This can be broken up into two loops:
for (i = 1; i <= n; i++){
for(j = 1; j <= 2*n; j += i) { // note: not j++
printf("Iteration %d : %d\n", i, j);
}
}
for (i = n+1; i <= 2*n; i++){
for(j = 1; j <= 2*n; j += i) { // note: not j++
printf("Iteration %d : %d\n", i, j);
}
}
In the first loop, it looks like the original loop, but the inner loop size has doubled. So, the first loop runs twice as long as the original algorithm.
For the second loop, the runtime is O(n), since the inner loop does 2 iterations for each value of i (excluding the last value of i, for which there is 1 iteration).
So, if T(n) is the runtime of your original algorithm, then
T(2n) = 2×T(n) + C×n
Which is equivalent to
T(n) = 2×T(n/2) + C×n/2
Which is recognizable as the typical binary divide and conquer complexity of O(n lg n).
j += iin the inner loop; that changes it. Now I don't know :-)