Laboration 1.3, Group 28

This is a hand-in written by **Mazdak Farrokhzad** and **Niclas Alexandersson** in **group 28** for the 3rd assignment on Lab1.

The assignment is about analysing an algorithm written in 3 different ways where all of them are functionally equivalent. The methods are available in the appendix.

a. Description of what the algorithm does

b. Complexity analysis

c. Testing and numerical analysis

The algorithm finds the sum of the first subsequence of numbers that has the greatest non-negative sum in an array of numbers. This may sound cryptic, so lets shed some light on it with an illustration.

If we have e.g. the sequence `[1, 2, 3, 4]`

it will yield the sum 10,
and the indexes will be `seqStart = 0, seqEnd = 3`

- thus it will simply return the sum of the whole sequence.

Instead, lets use the sequence `[-1, 2, 3, 4, -10, 5]`

.

In this case the subsequence will be the sum `[2, 3, 4] = 9`

,
and the indexes will be `seqStart = 1, seqEnd = 3`

.

Why? The first number, -1, will be skipped since it is negative.
The sequence will then stop at 4 when it finds that `9 + -10 = -1`

.
5 is < 9, and therefore, 9 is the sum.

These summation laws/formulas are used frequently. They are very common and thus we won’t prove any of them. Most of them can be found here

\(\displaystyle\sum_{n=s}^t C\cdot f(n) = C\cdot \sum_{n=s}^t f(n)\)

\(\displaystyle\sum_{n=s}^t f(n) + \sum_{n=s}^{t} g(n) = \sum_{n=s}^t \left[f(n) + g(n)\right]\)

\(\displaystyle\sum_{n=s}^t f(n) - \sum_{n=s}^{t} g(n) = \sum_{n=s}^t \left[f(n) - g(n)\right]\)

\(\displaystyle\sum_{i=m}^n 1 = n+1-m \Rightarrow \sum_{i=m}^{n-1} 1 = n-m\)

\(\displaystyle\sum_{i=m}^n i = \frac{n(n+1)}{2} - \frac{m(m-1)}{2} \Rightarrow \sum_{i=m}^{n-1} i = \frac{n(n-1)}{2} - \frac{m(m-1)}{2}\)

\(\displaystyle\sum_{i=0}^n i^2 = \frac{n(n+1)(2n+1)}{6} = \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6}\)

The 3 nested loops takes in worst case: \(ne * nd * nc = n^3 * cde = kn^3\).

**Conclusion:** The algorithm computes with \(\mathcal{O}(n^3)\) time complexity.

The mathematically correct estimate is represented by the function \(T(n)\).

Define the function as: \[T(n) = a + \sum_{i=0}^{n-1} f_3(n) = a + \sum_{i=0}^{n-1} (b + \sum_{j=i}^{n-1} (c + \sum_{k=i}^{j} d))\] Each loop in the method corresponds to one sum or one method \(f_i\) where the lowest index is the innermost sum/loop.

Define the other functions: \[\begin{aligned} f_1(j,i) &=\sum_{k=i}^j d = d \sum_{k=i}^j 1 = d(1 + j - i) = d + dj - di,\\ f_2(n,i) & = \sum_{j=i}^{n-1} (c + f_1(j,i)) \\ & = c\sum_{j=i}^{n-1} 1 + d\sum_{j=i}^{n-1} 1 + d\sum_{j=i}^{n-1} j - di\sum_{j=i}^{n-1} 1 \\ & = (c + d)\sum_{j=i}^{n-1} 1 + d(\frac{n(n-1)}{2} - \frac{i(i-1)}{2}) - di(n-i) \\ & = (c + d)\sum_{j=i}^{n-1} 1 + \frac{d}{2}n(n-1) + \frac{d}{2}i^2 + \frac{d}{2}(1-2n)i,\\ T(n) & = a + f_3(n) = a + \sum_{i=0}^{n-1} (b + f_2(n,i))\\ & = a + b\sum_{i=0}^{n-1} 1 + \sum_{i=0}^{n-1} f_2(n,i)\end{aligned}\]

Some substitution:

\[\begin{split} \sum_{i=0}^{n-1} f_2(n,i) & = (c+d)\sum_{i=0}^{n-1} (\sum_{j=i}^{n-1} 1) + \frac{d}{2}n(n-1)\sum_{i=0}^{n-1} 1 + \frac{d}{2}\sum_{i=0}^{n-1} i^2 + \frac{d}{2}(1-2n)\sum_{i=0}^{n-1} i \\ & = (c+d)\sum_{i=0}^{n-1} (n-i) + \frac{d}{2}n^2(n-1) + \frac{d}{2}(\frac{n(n-1)(2n-1)}{6}) + \frac{d}{2}(1-2n)\frac{1}{2}n(n-1) \\ & = \frac{1}{2}((c+d)(n^2 + n) + d(n^3 - n^2) + d(\frac{n^3}{3} - \frac{n^2}{2} + \frac{n}{6}) + \frac{d}{2}(1-2n)(n^2-n)) \end{split}\]

After some simplification, we are left with: \[\begin{aligned} \sum_{i=0}^{n-1} f_2(n,i) & = \frac{d}{6}n^3 + (\frac{c}{2}+\frac{d}{2})n^2 + (\frac{c}{2}+\frac{d}{3})n, \\ T(n) & = \frac{d}{6}n^3 + (\frac{c}{2}+\frac{d}{2})n^2 + (b + \frac{c}{2}+\frac{d}{3})n + a, \\\end{aligned}\]

Estimating constants:

method scope, outside all loops:

\(a = initMaxSum + outerLoopInit + outerLoopCondExtra + return = 1 + 1 + 2 + 1 = 5\)outer loop:

\(b = forLoopTurn + middleLoopInit + middleLoopCondExtra = 3 + 1 + 2 = 5\)middle loop:

\(c = forLoopTurn + initThisSum + innerLoopInit + innerLoopCondExtra + branch = \\ 3 + 1 + 2 + 8 = 14\)inner loop:

\(d = forLoopTurn + addThisSum = 3 + 1 = 4\)

Finally, substitute constants: \[T(n) = \frac{2}{3}n^3 + 9n^2 + \frac{40}{3}n + 5) \in \mathcal{O}(n^3)\]

The 2 nested loops takes in worst case: \(nd * nc = n^2 * cd = kn^2\).

**Conclusion:** The algorithm computes with \(\mathcal{O}(n^2)\) time complexity.

The mathematically correct estimate is represented by the function \(T(n)\).

Define the function as: \[T(n) = a + \sum_{i=0}^{n-1} f_2(n) = a + \sum_{i=0}^{n-1} (b + \sum_{j=i}^{n-1} c)\] Each loop in the method corresponds to one sum or one method \(f_i\) where the lowest index is the innermost sum/loop.

Define \(f_2(n)\): \[f_2(n) = \sum_{i=0}^{n-1} (b + f_1(n,i)) = b\sum_{i=0}^{n-1} 1 + \sum_{i=0}^{n-1} f_1(n,i)\]

Define \(f_1(n,i)\): \[f_1(n,i) = \sum_{j=i}^{n-1} c = c\sum_{j=i}^{n-1} 1 = c(n-i)\]

Substitute in \(f_2\) with \(f_1\) and simplify: \[\begin{split} f_2(n) & = b\sum_{j=i}^{n-1} 1 + c\sum_{j=i}^{n-1} (n-i) \\ & = bn + cn\sum_{j=i}^{n-1} 1 - c\sum_{j=i}^{n-1} i \\ & = bn + cn^2 - \frac{c}{2}n(n-1) \\ & = (c - \frac{c}{2})n^2 + (b + \frac{c}{2})n \\ & = \frac{c}{2}n^2 + (b + \frac{c}{2})n \end{split}\]

Substitute in \(T(n)\) with \(f_2\) \[T(n) = \frac{c}{2}n^2 + (b + \frac{c}{2})n + a\]

Estimating constants:

method scope + etc.:

\(a = initMaxSum + outerLoopInit + outerLoopCondExtra + return = \\ 1 + 1 + 2 + 1 = 5\)outer loop:

\(b = forLoopTurn + initThisSum + innerLoopInit + innerLoopCondExtra = \\ 3 + 1 + 1 + 2 = 7\)inner loop:

\(c = forLoopTurn + addThisSum + branch = \\ 3 + 2 + 8 = 13\)

Finally, substitute constants: \[T(n) = \frac{1}{2}(13n^2 + 27n + 10) \in \mathcal{O}(n^2)\]

## Share on Social Media