Complexity of this function ??

Question

void compute(int n) {
        int h = n;
        while (h > 1) {
            for (int i = 0; i < n; i++) {
                // do some operation
            }
            h = h / 2;
        }
 }

Can anybody please tell me what is the complexity( Big O ) of this function of n ??

This is actually an argument between me and a friend of mine. my stand: complexity is O(n*log(n)) friend's stand: log(n)

Thanks for your responses.

Answer 1

If this is homework (and it sounds a bit like it), then you should first try yourself.

Basically to get the complecity you look at the structure of the function, that is loops, nesting loops, etc. and determine how long they run, which inputs they depend on, etc.

In this case you have only one input, n. The local variable h starts with the same value as n, so it's essentially the same, complexity-wise, however, you need to keep track of how it's used.

You have essentially two nested loops here, one that runs to n, another one around it, that causes h to halve each time it's run. So this function is in O(n · log₂n).

Answer 2

It appears to be O(n.sqrt(n))

The outer loop is obviously n, and the inner loop is sqrt(n).

EDIT: The inner loop is correctly log(n), because the number of iterations is x where 2^x = n.

Answer 3

I'd say since in every run, h is halved and n operations are done, it's O(n * log n).

Answer 4

Some operation:

O(x)

The for loop: because n >= h and supposing h will not be modified during "some operation":

O(n*x)

The outer while loop:

O(log(n)*n*x)

Answer 5

Execution time graphs:

Answer 6

Anyone who says this function is log(n) is not your friend.

Answer 7

It is clearly n*log(h).