I'm stuck with nested for loops that are dependent on the previous loop:

for (i=1; i<=n; i++)
  for (j=1; j<=i; j++)
    x = x+1 

the part that is confusing me is j<=i. I'm trying to figure out the asymptotic running time.

  • $\begingroup$ Just to be clear, I'm guessing that what you've talking about is code something like: for i=0; i<n; i++ { for j = 1; j<=i; j++ { x = x + 1 } }, and you're trying to figure out the computational complexity? $\endgroup$ Feb 10 at 5:43
  • $\begingroup$ Compare $\sum\limits_{i=1}^n n$ and $\sum\limits_{i=1}^n i$. $\endgroup$
    – greybeard
    Feb 10 at 8:31
  • 1
    $\begingroup$ In what sense are you stuck? Are you trying to understand what the code is doing? Are you trying to figure out the asymptotic running time? Try to be more verbose when asking a question. $\endgroup$ Feb 10 at 9:00

Suppose that you start with some value in $x$. The inner loop increases $x$ by $i$. Therefore the outer loop increases $x$ by $1+2+3+\cdots+n = n(n+1)/2$. So overall, your code increases the value in $x$ by $n(n+1)/2$.

The running time of your code is proportional to the number of times that $x$ is increased, hence it is $\Theta(n^2)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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