According to my professor, the following code has a time complexity of O(N), but I don't understand why time complexity is so.
int sum = 0;
for (int i=1; i<n; i=i*3) {
for (int j=1; j<=i; j++) {
sum++;
}
}
From how I see it, the outer loop is O(logN) and the inner loop is O(i*N).
So shouldn't the time complexity be O(i*N) * O(logN) = NlogN?
The inner loop will perform the following number of iterations:
1 for the 1st outer iteration
3 for the 2nd outer iteration
9 for the 3rd outer iteration
...
~n for the last outer iteration.
I.e. the inner loop will totally run 1+3+9+ ... + ~n times.
This is a geometric series with O(logn) elements, and the sum of it is O(n).
This is because the gemeral sum of a geometric series starting with a1, witha ratio of r and with x elements is:
Sx = a1 * (1 - r^x) / (1 - r)
If you use 1 for a1, 3 for r, and logn for x, you will get:
Slogn = 1 * (1 - 3^logn) / (1 - 3)
And since 3^logn is O(n), the whole expression is O(n).