Вывод времени выполнения для тройного вложенного цикла

Question

Мне пришлось решить проблему, которая потребовала от меня выяснения времени выполнения для этого фрагмента кода:

for (i = 1; i <= log(n); i = i + 1) {
    for (j = 1; j <= 2*i; j = 2*j) {
        for (k = 1; k <= log(j); k = k + 1) {
            print("[some arbitrary string]");
        }
    }
}

Из проверки очевидно, что это Θ((log(n)^3), поскольку каждый из for loops - это Θ(log(n)), но я не совсем уверен, каков наилучший способ доказать это (например, с помощью сумм).

Answer 1

Заменим log(n) на x (x = log(n)).Затем

for (i = 1; i <= x; i = i + 1) {
    for (j = 1; j <= 2*i; j = 2*j) {
        for (k = 1; k <= log(j); k = k + 1) {
            print("[some arbitrary string]");
        }
    }
}

Во втором цикле j проходит через степени 2.Давайте возьмем другой цикл с той же асимптотикой, используя другую подстановку: y = log(j):

for (i = 1; i <= x; i = i + 1) {
    for (y = 0; y <= log(i); ++y) {
        for (k = 1; k <= y; k = k + 1) {
            print("[some arbitrary string]");
        }
    }
}

Сложность O(x * log(x)^2) = O(log(n) * log(log(n))^2).