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

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. $$

  • $\begingroup$ can you please solve the complete expression. I'm not getting the correct answer to it. $\endgroup$ – Ahsan Shabbir May 3 '20 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$ – Yuval Filmus May 3 '20 at 20:53

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.