javatime-complexitybig-o

Understanding Time Complexity of Geometric Progression Series


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?


Solution

  • 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).