A Loop That Doubles

Here is a contrived example of a loop where the loop counter is multiplied by a constant each iteration, rather than added to.

public int myStrangeSum(int num) {
  int sum = 0;
  for (int i = 1; i < num; i *= 2) {
    sum += i;
  }

  return sum;
}

Let $n$ be the value of num. What is the Big-Oh of this method?

The body of the loop is constant work, so the only question is how many times the loop runs. i doubles each iteration instead of going up by one. It takes the values $1,2,4,8,16,\dots$, and the loop stops once i reaches or passes $n$, because the condition is i < num.

So how many doublings does it take to get from $1$ up to $n$? That is the same question we asked about binary search. There we kept halving $n$ until we got down to $1$, and the answer was ${\log }_{2}n$. Here we keep doubling $1$ until we get up to $n$. The values are the same, $1,2,4,8,\dots ,n$. We just go through them in the other direction, so there are the same number of them. If it helps to see the halving version directly, this loop runs the same number of times:

for (int i = num / 2; i > 0; i /= 2) {
  sum += i;
}

Take $n$ to be a power of two if you want the counts to match exactly. When $n$ is not a power of two, the two counts can be off by one, and one step does not change how the work grows.

Either way, the loop runs about ${\log }_{2}n$ times, and the body is constant work, so this method is $O(\log n)$.

When a loop counter is multiplied or divided by a constant each time, rather than added to, the loop runs a logarithmic number of times.