Time complexity which the loop is controlled by condition like i = c^i, c is a constant

a problem about time complexity

int j = 2
while (j < n) {
    int k = j
    while (k < n) {
        sum += a[k] * b[k]
        k += n^1/3 * logn
    }
    j = 2^j
}

The execution time of inner loop seems to be ((n-2) / n^1/3 * logn) + 1, however I am not sure how many times the outer loop executes which is controlled by condition j = 2^j. Thank u so much!

1 answer

  • answered 2018-11-08 19:49 Andreas

    Assuming int is 32-bit type, if n > 65536, it will run forever because of overflow. For n <= 65536, the progression of j is 2, 4, 16, 65536, which means that outer loop iterates at most 3 times, not an ever-growing number relative to n, so outer loop can be considered O(1).