What is the complexity of the following method?

Question

Hello, I'm still learning about complexity measurement using the Big O Notation, was wondering if I'm correct to say that following method's complexity is O(n*log4n), where the "4" is a subscript.

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

Answer 1

Yes, You are correct, that the complexity of the function is O(n*log_4(n))

Log_4(n) = ln(n) / ln(4) and ln(4) is a constant, so if Your function has complexity O(n*log_4(n)) it is also true, that it has a complexity of O(n*ln(n))

Answer 2

Did you mean

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; 
    } 
} 

?

In that case, too you are correct. It is O(nlogn). Using the 4 as subscript is correct too, but it only makes it more cumbersome to write.

Even with the j=n line, it is O(nlogn).

In fact to be more accurate you can say it is Theta(n logn).

Answer 3

yes you are right, complexity is n* log4(n)