0
$\begingroup$

There are two nested for loops. I'm not sure but I think that it's geometric series, but I cannot get well solution for it. What I tried is below up to now,

$$ \sum _{i=0}^{log\left(n-1\right)}\:\sum _{j=0}^{i-1}\:1 $$ $$ \sum _{i=0}^n\:\sum _{j=0}^n\:\left(\frac{1}{2}\right)^j $$

At first, I thought it's $O(nlogn)$ but instead as far as I research the right result is $O(n)$.

int try(int n) {   
    int sum = 0;   
    for (int i = n; i > 0; i /= 2) {     
        for (int j = 0; j < i; j++) {      
          sum += 1; 
          }
    }  
    return sum;
} 

Could you show its sigma notation with its complexity? I want to comprehend it.

$\endgroup$
  • $\begingroup$ Are you sure your return statement is aligned correctly? Also, is your question about algorithm complexity? or how big is the output? $\endgroup$ – Siong Thye Goh Oct 14 '17 at 23:40
  • $\begingroup$ it's aligned now better and about algorithm complexity. @SiongThyeGoh $\endgroup$ – itsnotmyrealname Oct 15 '17 at 0:37
0
$\begingroup$

The complexity is basically how many times the "sum+=1;" line is executed, since it is the line that is executed most often. How many times then?

$$n+\lfloor\frac{n}{2}\rfloor+\lfloor\frac{n}{2^2}\rfloor+\cdots\leq n+\frac{n}{2}+\frac{n}{2^2}+\cdots=2n.$$

So the time complexity is $\mathcal{O}(n)$, as the run time of the code is bounded by a constant times $n$.

$\endgroup$
  • $\begingroup$ I have found the solution but I can't grasp it. $ \frac{n}{\:2}+\:\frac{n}{4}\:+\:\frac{n}{8}+\:...\:+\:\frac{n}{n^2} $. How did you obtain it? Also, could you show its sigma notations? $\endgroup$ – itsnotmyrealname Oct 15 '17 at 9:07
  • $\begingroup$ The sigma notation is $\sum_{k=0}^\infty\lfloor\frac{n}{2^k}\rfloor$ for the left-hand side. The floor is less than equal to the number itself. Then we sum a geometric series. There are only a finite number of nonzero terms in the sum of floors. Every term corresponds to one value of $i$. $\endgroup$ – Zhuoran He Oct 15 '17 at 15:56

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.