# Running-time cost of Tweaked Nested Loop

I understand that the following nested for-loop:

for(i=0; i<n/2; i++)
for(j=0; j<n/2; j++)
print(j)


has the runtime complexity of

$\sum_{i=0}^{n/2}&space;\sum_{j=0}^{n/2}{1}&space;=&space;\sum_{i=0}^{n/2}{n/2}$

which has a simplifed complexity of

$n^{2}/4&space;=&space;O(n^{2})$

but what is the resulting complexity of making j bound to i/2 in the inner loop? For instance:

for(i=0; i<n/2; i++)
for(j=0; j<i/2; j++)
print(j)


Would this be

$\sum_{i=0}^{n/2}&space;\sum_{i=0}^{log(logn)}1$

?

• Don't use "complexity" for everything. Also, your derivations are subtly wrong; check the summation bounds. Mar 23, 2016 at 9:01
• Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. Mar 23, 2016 at 9:02
• Wherer did the $\log \log n$ upper summation bound come from? Why don't you translate the loop into a sum literally? Mar 23, 2016 at 9:03

The complexity would be

$$\sum_{i = 0}^{n/2-1} \sum_{j = 0}^{i/2-1} 1\,,$$ which is $O(n^2)$.

It is also $O(n^2)$. Because

for(i=0; i<n/2; i++)
for(j=0; j<i/2; j++)
print(j)


is asymptotically equivalent to

for(i=0; i<n; i++)
for(j=0; j<i; j++)
print(j)


which calls the print statement $n \times (n - 1)$ many times.

• Why are these two things asymptotically equivalent? (And what exactly do you mean by "asymptotically equivalent"?) It seems that anyone who could see that the two programs you've quoted are equivalent wouldn't need to ask the question, so this answer seems unlikely to be very helpful to the asker. Feb 22, 2016 at 2:31
• As David mentioned, I'm not entirely clear on how they are asymptotically equivalent. Is this because the second program still exhibits the hallmark behavior of O(n^2) by increasing the ouput by four-fold when n is doubled....? Feb 22, 2016 at 17:23