Time complexity of nested loop with dependent inner index-CodePudding

Looking to compute the complexity of the following loop

int f(int N) {
    int count = 0;
    for (int i = 1; i < N; i *= 3) {
        for (int j = 1; j < i;   j) {
            count  ;
        }
    }
    return count;
}

For the first loop, the values of i are like the following: 1, 3, 9, 27, 81, .., 3^m

where 3^m <= N < 3^{m 1}

Then 3^m = c * N for some constant c

log_3(3^m) = log_3(c*N)

m * log_3(3) = log_3(c * N) m = log_3(c) log_3(N)

which implies a complexity O(log_3(c) log_3(N)) ~ O(log_3(N)) ~ O(log_2(N)) ~ log(N)

for every i from the first loop executed, the second loop is executed 3^(i-1). Following the same reasoning as before, the complexity ends up log(N), so that the overall complexity should be the multiplication of the 2, i.e. log(N)**2.

Is this computation correct for the complexity of these nested loops?

CodePudding user response：

Log3(n) is correct for the outer loop. Big-O doesn't take into account constants, so the inner loop, being linear, is O(n). This makes the entire thing O(n log n).

CodePudding user response：

The outer loop is O(log(N)), the inner loop is O(N) - the amortized geometric row 3 9 27 ... n, n is some value between N/3 and N-1. The overall complexity is O(N * log(N)).

It seems there are questions to the sum.

3 9 27 ... n is 1 3 9 27 ... n - 1 is (3^n - 1)/(3-1) - 1, n is log_3(N), thus this is (N - 1)/2 - 1, that is O(N).