Solving Triple Summation with Dependent Index Lower Limit to Analyze Triple For Loop Runtime

Problem:

Here, instead of analyzing the runtime line by line, I will only only analyze the three for loops in the code below. Everything else is taken as $ O(1) $.
I am ignoring the while loop and will only analyze for loops. An easy way to estimate approximate running time is by looking at the three for loops we can see the the algorithm below is cubic.

---

Code:

---

Analyzing For Loops:

In the code above the innermost for loop is dependent on middle for loop and the middle for loop is dependent on outer for loop.

The for code, for(i = 1; i <= N / 2; ++i ) can be written as, $ \sum_{i=1}^{\frac{N}{2}} $

Similarly, for(j = i; j <= N / 2; ++j ) can be written as, $ \sum_{j=i}^{\frac{N}{2}} $ and for(k = j; k <= N / 2; ++k ) can be written as, $ \sum_{k=j}^{\frac{N}{2}} $.
Now it is in the format below,
$ f(n) = \displaystyle\sum_{i=1}^{\frac{N}{2}} \sum_{j=i}^{\frac{N}{2}} \sum_{k=j}^{\frac{N}{2}} 1 $

If the above is put on wolfram alpha it gives,
$ \displaystyle\sum_{i=1}^{\frac{N}{2}} \sum_{j=i}^{\frac{N}{2}} \sum_{k=j}^{\frac{N}{2}} 1 = \frac{1}{48} N (N^2+6 N+8) $
Now task is to prove the above.

---

Proof:

$ f(n) = \displaystyle\sum_{i=1}^{\frac{N}{2}} \sum_{j=i}^{\frac{N}{2}} \sum_{k=j}^{\frac{N}{2}} 1 $
$ \ \ \ \ \ \ \ \ = \displaystyle\sum_{i=1}^{\frac{N}{2}} \sum_{j=i}^{\frac{N}{2}} ( \frac{N}{2} - j + 1 ) \qquad----(i) $

---

Side Note Proof, $ \sum_{k=j}^{\frac{N}{2}} 1 = ( \frac{N}{2} - j + 1 ) $:

$ \displaystyle\sum_{k=j}^{\frac{N}{2}} 1 = \sum_{k=1}^{\frac{N}{2}} 1 - \sum_{k=1}^{j-1} 1 $
$ \ \ \ \ \ \ \ \ = \frac{N}{2} * 1 - (j-1) * 1 $
$ \ \ \ \ \ \ \ \ = \frac{N}{2} - j + 1 $

---

Continuing from $ (i) $,
$ f(n) = \displaystyle\sum_{i=1}^{\frac{N}{2}} \sum_{j=i}^{\frac{N}{2}} ( \frac{N}{2} - j + 1 ) $
$ \ \ \ \ \ \ \ \ = \displaystyle\sum_{i=1}^{\frac{N}{2}} \Bigg( \sum_{j=i}^{\frac{N}{2}} ( \frac{N}{2} + 1 ) - \sum_{j=i}^{\frac{N}{2}} j \Bigg) $
$ \ \ \ \ \ \ \ \ = \displaystyle\sum_{i=1}^{\frac{N}{2}} \Bigg( \big( \frac{N}{2} + 1 \big) \sum_{j=i}^{\frac{N}{2}} 1 - \big( \sum_{j=1}^{\frac{N}{2}} j - \sum_{j=1}^{i-1} j \big) \Bigg) $
$ \ \ \ \ \ \ \ \ = \displaystyle\sum_{i=1}^{\frac{N}{2}} \Bigg( \big( \frac{N}{2} + 1 \big) \big( \frac{N}{2} - i + 1 \big) - \bigg( \frac{N}{4} \big( \frac{N}{2} + 1 \big) - \frac{i(i-1)}{2} \bigg) \Bigg) \qquad----(ii) $

---

Side Note:

$ \displaystyle\sum_{i=1}^{n} i = \frac{n(n+1)}{2} $
$ \displaystyle\sum_{i=1}^{\frac{N}{2}} i = \frac{\frac{N}{2}(\frac{N}{2}+1)}{2} = \frac{N}{4} \bigg( \frac{N}{2} + 1 \bigg) $
$ \displaystyle\sum_{i=1}^{i-1} i = \frac{(i-1)((i-1)+1)}{2} = \frac{i(i-1)}{2} $

---

Continuing from $ (ii) $,
$ f(n) = \displaystyle\sum_{i=1}^{\frac{N}{2}} \Bigg( \frac{N^2}{4} - \frac{Ni}{2} + \frac{N}{2} + \frac{N}{2} - i + 1 - \frac{N^2}{8} - \frac{N}{4} + \frac{i^2}{2} - \frac{i}{2} \Bigg) $
$ \ \ \ \ \ \ \ \ = \displaystyle\sum_{i=1}^{\frac{N}{2}} \Bigg( \frac{N^2}{8} - \frac{Ni}{2} + \frac{3N}{4} + 1 - \frac{3i}{2} + \frac{i^2}{2} \Bigg) $
$ \ \ \ \ \ \ \ \ = \displaystyle\sum_{i=1}^{\frac{N}{2}} \Bigg( \frac{N^2}{8} + \frac{3N}{4} + 1 + \frac{i^2}{2} - i \bigg( \frac{N}{2} - \frac{3}{2} \bigg) \Bigg) $
$ \ \ \ \ \ \ \ \ = \displaystyle \Bigg( \frac{N^2}{8} + \frac{3N}{4} + 1 \Bigg) \sum_{i=1}^{\frac{N}{2}} 1 + \sum_{i=1}^{\frac{N}{2}} \frac{i^2}{2} - \sum_{i=1}^{\frac{N}{2}} i \bigg( \frac{N}{2} - \frac{3}{2} \bigg) $
$ \ \ \ \ \ \ \ \ = \displaystyle \Bigg( \frac{N^2}{8} + \frac{3N}{4} + 1 \Bigg) \frac{N}{2} + \frac{1}{2} \sum_{i=1}^{\frac{N}{2}} i^2 - \bigg( \frac{N}{2} - \frac{3}{2} \bigg) \sum_{i=1}^{\frac{N}{2}} i $
$ \ \ \ \ \ \ \ \ = \displaystyle \Bigg( \frac{N^2}{8} + \frac{3N}{4} + 1 \Bigg) \frac{N}{2} + \Bigg( \frac{1}{2} * \frac{1}{6} * \frac{N}{2} ( \frac{N}{2} + 1 ) ( N + 1 ) \Bigg) - \bigg( \frac{N}{2} - \frac{3}{2} \bigg) \frac{N}{4} \bigg( \frac{N}{2} + 1 \bigg) $
$ \ \ \ \ \ \ \ \ = \displaystyle \Bigg( \frac{N^3}{16} + \frac{3N^2}{8} + \frac{N}{2} + \frac{N^3}{48} + \frac{N^2}{48} + \frac{N^2}{24} + \frac{N}{24} - \frac{N^3}{16} - \frac{N^2}{8} - \frac{3N^2}{16} - \frac{3N}{8} \bigg) $
$ \ \ \ \ \ \ \ \ = \displaystyle \Bigg( \frac{N^3}{48} + \frac{3N^2}{16} - \frac{3N^2}{48} + \frac{4N}{24} \bigg) $
$ \ \ \ \ \ \ \ \ = \displaystyle \Bigg( \frac{N^3}{48} + \frac{N^2}{8} + \frac{N}{6} \bigg) $
$ \ \ \ \ \ \ \ \ = \displaystyle \frac{1}{48} N \Bigg( N^2 + 6N + 8 \bigg) $

---

So finally,
$ f(n) = \displaystyle \frac{1}{48} N \Bigg( N^2 + 6N + 8 \bigg) $
$ f(n) \in O(N^3) $

Since, the equation has highest degree of $ 3 $, it dominates over other terms. So, this is a cubic equation with $ O(N^3) $ runtime.

---