# The number of executions of the count statement; how many?

How many times does the statement count in line 5 executes in terms of $n$?

1.  count=0;
2.  for (i=1; i<=n; i++) {
3.  for (j=1; j<=n; j*=2) {
4.  for (k=1; k<=j; k++) {
5.        count = count + 1;
6.      }
7.    }
8.  }


For the loop in line 3, we can list the numbers for $j$ as, $2^0,2^1,...,2^{\log n}$ Therefore, we can refer to the iterations of the exponents as $r$. Doing so would lead to the summations below for counting the number of executions.

$\sum_{i=1}^{n}\sum_{r=0}^{\log n}\sum_{k=1}^{j}1 =\sum_{i=1}^{n}\sum_{r=0}^{\log n}j$

I am stuck here, because $\sum_{r=0}^{\log n}$ depends on $j$ but I am not sure how to incorporate them.

Hint: Substitute $j = 2^r$, and use the formula for summing a geometric series.
Make sure that you understand why the substitution $j = 2^r$ makes sense.
• Thanks a million. I can't believe I missed that. That part of the summation should be, $\sum_{r=0}^{\log n}2^r = \frac{2^{\log n + 1} - 1}{2-1} = 2^{\log n + 1} - 1$ :) – Curious Mar 1 '14 at 5:26