title: Calculating complexity?
body: <p>I've been trying to calculate the complexity of the following function:</p>
  
  <pre><code>k=n;
  while(k&gt;0)
    g(n);
    k=k/2; {Comment: this is integer division, so 1/2=0}
  end while;
  for(j=0;j&lt;m;j++)
    f(m);
  </code></pre>
  
  <p>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?</p>