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

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

Answer 2

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