Calculating complexity?

Question

I've been trying to calculate the complexity of the following function:

k=n;
while(k>0)
  g(n);
  k=k/2; {Comment: this is integer division, so 1/2=0}
end while;
for(j=0;j<m;j++)
  f(m);

Specifically, the complexity of the while loop.I am told that g(n)'s complexity is O(n), but I'm not sure what the complexity would be for it, and how I would work it out. I have come to realise that the complexity would not be O(0.5n^2), but am unsure how to calculate it, because of the halving each time. Anyone have any ideas?

Answer 1

If g(n) is O(n), then your complexity is O(n*log(n))

To explain further, let us ignore g(n) for the moment

k = n;
while(k > 0) {
    k = k / 2;
}

Let say n = 1000

Then we will get the following values of k

Pass | k
-------------
 0   | 1000
 1   | 500
 2   | 250
 3   | 125
 4   | 62
 5   | 31
 6   | 15
 7   | 7
 8   | 3
 9   | 1
 10  | 0 (stopped)

log(1000) = 9.96 Note it only took 10 iterations to bring down k to zero. This is an example of a log(n) computational complexity.

Then when you add the g(n) inside the loop, that means you add O(n) for every iteration, which gives us a grand total of O(n*log(n))