CODEWITHSUNDEEP
complexity-theorybig-o
George Kagan
George Kagan

Reputation: 6124

What is the complexity of the following method?

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

Upvotes: 1

Views: 321

Answers (3)

svlada
svlada

Reputation: 3288

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

Upvotes: 1

Maciej Hehl
Maciej Hehl

Reputation: 7985

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))

Upvotes: 6

Aryabhatta
Aryabhatta

Reputation:

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).

Upvotes: 3

Related Questions