What is the time complexity of the following triple nested loop? Kindly solve in term of n

Question

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)

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