-2
$\begingroup$

I want to ask that what is the time complexity of this function (triple nested loop) .Kindly analysis completely so that I can understand.

function loop_nested(n)
  r := 0
  for i := 1 to n - 1 do
    for j := i + 1 to n do
      for k := 1 to j do
        r := r + 1
  return(r)
$\endgroup$
2

1 Answer 1

1
$\begingroup$

The value of $r$ at the end is $$ \sum_{i=1}^{n-1} \sum_{j=i+1}^n \sum_{k=1}^j 1 = \sum_{i=1}^{n-1} \sum_{j=i+1}^n j. $$ You take it from here. You can use a computer algebra system such as Wolfram alpha to help you with the calculations.

If you are only interested in asymptotics, then you can use the following upper bound: $$ \sum_{i=1}^{n-1} \sum_{j=i+1}^n j \leq \sum_{i=1}^n \sum_{j=1}^n n. $$ I'll let you work out what upper bound this gives. It turns out that this upper bound is quite good, as you can verify using the following lower bound (valid for large $n$): $$ \sum_{i=1}^{n-1} \sum_{j=i+1}^n j \geq \sum_{i=1}^{n/2} \sum_{j=n/2+1}^n n/2. $$

$\endgroup$
2
  • $\begingroup$ can you please solve the complete expression. I'm not getting the correct answer to it. $\endgroup$ May 3, 2020 at 20:53
  • $\begingroup$ Unfortunately, that's something I'm not willing to do. The folks at Mathematics will be happy to do it for you. $\endgroup$ May 3, 2020 at 20:53

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.