The 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 someone please tell me what the complexity (Big O) of this function n is?

This is actually an argument between me and my friend. my stand: complexity O (n * log (n)) friendly stand: log (n)

Thank you for your responses.

Answer 1

I would say that in each run h is halved and n operations are performed, O (n * log n).

Answer 2

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

Basically, to get complete, you look at the structure of the function, that is, at the loops, nesting loops, etc., and determine how long they work, what inputs depend on them, etc.

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

Here you have essentially two nested loops, one of which works with n, the other around it, which causes h to be halved each time it starts. So this function is in O (n · log ₂ n).

Answer 3

Some operation:

 O(x) 

The for loop: since n> = h and assuming h will not be changed during "some operation":

 O(n*x) 

External while loop:

 O(log(n)*n*x) 

Answer 4

It seems that O (n.sqrt (n))

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

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

Answer 5

This is explicitly n * log (h) .