# Complexity Analysis of Nested Loops with Sigma Notation

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.

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

$$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$.
• 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? – itsnotmyrealname Oct 15 '17 at 9:07
• 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$. – Zhuoran He Oct 15 '17 at 15:56