Какова сложность следующего метода?

Question

Я все еще учусь измерять сложность, используя обозначение Big O, мне было интересно, правильно ли я сказал, что сложность следующего метода равна O (n * log4n) , где "4" нижний индекс.

public static void f(int n)
{
    for (int i=n; i>0; i--)
    {
        int j = n;
        while (j>0)
            j = j/4;
    }
}

Answer 1

Да, Вы правы, сложность функции составляет O(n*log_4(n))

Log_4(n) = ln(n) / ln(4) и ln(4) - это константа, поэтому, если ваша функция имеет сложность O(n*log_4(n)), это также верно, что она имеет сложность O(n*ln(n))

Answer 2

Вы имели в виду

public static void f(int n) 
{ 
    for (int i=n; i>0; i--) 
    { 
        int j = i;  // Not j = n.
        while (j>0) 
            j = j/4; 
    } 
} 

В этом случае вы тоже правы. Это O (nlogn). Использование 4 в качестве нижнего индекса тоже правильно, но это только усложняет написание.

Даже со строкой j=n это O (nlogn).

На самом деле, чтобы быть более точным, вы можете сказать, что это Theta (n logn).

Answer 3

да, вы правы, сложность n * log4 (n)