Running-time cost of Tweaked Nested Loop

Question

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} \sum_{j=0}^{n/2}{1} = \sum_{i=0}^{n/2}{n/2}$

which has a simplifed complexity of

$n^{2}/4 = 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} \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, 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. — Raphael, 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? — Raphael, Mar 23, 2016 at 9:03

David Richerby · Accepted Answer · 2016-02-22 01:54:14Z

1

The complexity would be

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

David Richerby

81.4k26 gold badges139 silver badges234 bronze badges

answered Feb 21, 2016 at 23:44

vonbrand

13.9k3 gold badges39 silver badges50 bronze badges

Add a comment |

erensezener · Accepted Answer · 2016-02-21 23:48:17Z

0

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.

answered Feb 21, 2016 at 23:48

erensezener

2481 silver badge8 bronze badges

1

$\begingroup$ 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. $\endgroup$
– David Richerby
Feb 22, 2016 at 2:31
$\begingroup$ 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....? $\endgroup$
– TacoB0t
Feb 22, 2016 at 17:23

Add a comment |

2 Answers 2