Exercise VI

Consider the following program

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

  return sum; 
}

Exercise What is the asymptotic running time of the code above as a function of $n$ where $n$ is the value of num?

A) $O(n^2)$
B) $O(\lg n)$
C) $O(2^n)$

Solution

The answer is $O(\lg n)$.

It might be easier to understand this if, without lack of generality, we assume num is a power of $2$ and rewrite the loop as 

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

How many times can you divide num (i.e., $n$) to get to $1$? We answered this question when we analyzed the running time of the binary search algorithm. The answer was $\lg n$.

Resources

This video might be helpful: Deeply Understanding Logarithms In Time Complexities & Their Role In Computer Science.