0
$\begingroup$

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

which has a simplifed complexity of

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

?

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

2 Answers 2

1
$\begingroup$

The complexity would be

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

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$
2
  • 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$ 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.