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.

Thanks in advance.


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.

  • $\begingroup$ 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$ :) $\endgroup$ – Curious Mar 1 '14 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.