CODEWITHSUNDEEP
ccomplexity-theory
sLang
sLang

Reputation: 3

Need help of calculating the complexity of a code

I have a small code that I need to know the complexity of and can't figure it out myself, can someone help/guide me to the solution?

int funn(int n) {
    int i, j, k = 0;
    for (i = n / 2; i <= n; i++)
        for (j = 2; j <= n; j = j * 2)
            k = k + n / 2;
    return k;
}

at first, I thought that the complexity is O(n) but there are some multiplications that I'm not sure of. I'm new to that stuff so I need a guidance

Upvotes: 0

Views: 58

Answers (1)

John Zwinck
John Zwinck

Reputation: 249133

The outer loop is (n/2) which is O(n). The inner loop is O(log n).

So the whole thing is O(n log n).

Upvotes: 3

Related Questions