Can someone evaluate the time complexity of this function

Question

function    (n)
input : an  integer n
r ← 0
for i = 1 to n  //runs n times
    for j = i   + 1 to n     // runs n^2 times
           for k = i + j − 1 to n   //runs n^3 times
                r ← r + 1
return r

My answer was O(n^3), but when I tried finding it using sigma notation it always ends up being O(n^2).

Original question:

What value is returned by the following algorithm? What is its basic operation? How
many times is the basic operation executed? Give the worst-case running time of the
algorithm using Big Oh notation.

Answer 1

tldr: The algorithm is in O(n^3).

---

Why?

Count how often r <- r + 1 is executed.

If it helps, implement it in some language and execute it to get a better feeling for it. For example in Java:

int n = 10;

int r = 0;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        for (int k = i + j - 1; k <= n; k++) {
            r++;
        }
    }
}

---

Introduction

The outer loop generates n iterations, correct. The second loop will then generate n - 1, n - 2, n - 3, n - 4, ... generations.

The innermost loop however depends on i, j and n.

Example, fix i = 1 and let j run from n - 1 to 1. You will get k 1 + (n - 1) to n which are no runs at all. Then 1 + (n - 2) to n which are 2 runs, up to n runs.

So with i = 1 you will get k = 2, 3, 4, ..., n. Then i = 2 and you get k = 4, ..., n + (n + 1). This repeats and sums up until i = n yields only k = (n+(n-2)), in total:

i = 1 -> k = 2, 3, 4, 5, 6, ..., n
i = 2 -> k =       4, 5, 6, ..., n, (n+1)
i = 3 -> k =             6, ..., n, (n+1), (n+2)
  .
  .
  .
i = n -> k =                  (n+(n-2))

For the example with n = 10 this is:

2, 3, 4, 5, 6, 7, 8, 9, 10 
      4, 5, 6, 7, 8, 9, 10, 11
            6, 7, 8, 9, 10, 11, 12
                  8, 9, 10, 11, 12, 13
                        10, 11, 12, 13, 14
                                12, 13, 14, 15
                                        14, 15, 16
                                                16, 17
                                                        18

for k.

---

Values for k

Now note that the loop only executes until k <= n. So you can discard all values for k higher than n and count the iterations for the remaining values.

2, 3, 4, 5, 6, 7, 8, 9, 10| 
      4, 5, 6, 7, 8, 9, 10|, 11
            6, 7, 8, 9, 10|, 11, 12
                  8, 9, 10|, 11, 12, 13
                        10|, 11, 12, 13, 14
                          |     12, 13, 14, 15
                          |             14, 15, 16
                          |                    16, 17
                          |                           18

---

Total runs

So each of those is a value for k and it will generate (n + 1) - k many runs. So do that and you get:

9, 8, 7, 6, 5, 4, 3, 2, 1
      7, 6, 5, 4, 3, 2, 1
            5, 4, 3, 2, 1
                  3, 2, 1
                        1

Sum those up and you finally get the amount of total runs:

9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1
      + 7 + 6 + 5 + 4 + 3 + 2 + 1
              + 5 + 4 + 3 + 2 + 1
                      + 3 + 2 + 1
                              + 1

Which yields r = 95.

---

Formula and proof

The exact formula for that is:

sum_{i = 1}^{n - 1} ceil((n - i) / 2) * i

If you drop the ceil (it wont affect the complexity) you can simplify this to

n^3 / 12 - n / 12

And now you can easily see and prove that this is in O(n^3).