Большая сложность двух вложенных циклов

Question

Я пытаюсь найти сложность Big-O следующего алгоритма:

int i, j;
for (i = 0; i < n; i += 5)
{
    for (j = 1; j < n; j *= 3)
    {
        // O(1) code here
    }
}

n размер массива, переданного в метод. Борьба с этим из-за i += 5 а также j *= 3, Я знаю, что это, вероятно, неправильно, но я попробовал следующее...

• Внешний цикл повторяется n/5 раз. Это просто O(n)?

• Внутренний цикл повторяет log3(n) раз. Должно быть просто войти (n).

• Так как они вложенные, умножьте сложности вместе.

• Таким образом, сложность Big O - это просто O(n log(n))?

Answer 1

Вы можете действовать следующим образом:

Answer 2

Да ты прав. временная сложность n(log n) - база 3.

Попробуйте взять очень большое входное значение для n, и вы поймете, что график для [(n/5)*(log3n)] работает идентично. Надеюсь это поможет.