Временная сложность, которой цикл управляет условие типа i = c ^ i, c является константой

Question

проблема о временной сложности

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
}

Кажется, что время выполнения внутреннего цикла составляет ((n-2) / n ^ 1/3 * logn) + 1, однако я не уверен, сколько раз выполняется внешний цикл, который контролируется условием j = 2 ^ к. Большое спасибо!

Answer 1

Предполагая, что int является 32-битным типом, если n > 65536, он будет работать вечно из-за переполнения.Для n <= 65536 прогрессия j равна 2, 4, 16, 65536, что означает, что внешний цикл повторяется не более 3 раз, а не постоянно растущее число относительно nТаким образом, внешний цикл можно считать O (1) .