# 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. – Raphael Mar 23 '16 at 9:01
• Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – Raphael Mar 23 '16 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? – Raphael Mar 23 '16 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. – David Richerby Feb 22 '16 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....? – TacoB0t Feb 22 '16 at 17:23