Exercise VI

  • Use Big-Oh notation to describe the asymptotic runtime of a program.

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 nn where nn is the value of num?

A) O(n2)\Omicron(n^2)
B) O(lg⁡n)\Omicron(\lg n)
C) O(2n)\Omicron(2^n)

Solution

The answer is O(lg⁡n)\Omicron(\lg n).

It might be easier to understand this if, without lack of generality, we assume num is a power of 22 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., nn) to get to 11? We answered this question when we analyzed the running time of the binary search algorithm. The answer was lg⁡n\lg n.

Resources

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