ROUGH DRAFT authorea.com/4691

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

## The analysis consists of:

a. Description of what the algorithm does

b. Complexity analysis

c. Testing and numerical analysis

# Description of what the algorithm does

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.

# Complexity analysis

## Laws and forumulas of summation

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

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

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

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

4. $$\displaystyle\sum_{i=m}^n 1 = n+1-m \Rightarrow \sum_{i=m}^{n-1} 1 = n-m$$

5. $$\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}$$

6. $$\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}$$

## Version 1

### Rough estimate

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.

### Mathematically correct estimate

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:

1. method scope, outside all loops:
$$a = initMaxSum + outerLoopInit + outerLoopCondExtra + return = 1 + 1 + 2 + 1 = 5$$

2. outer loop:
$$b = forLoopTurn + middleLoopInit + middleLoopCondExtra = 3 + 1 + 2 = 5$$

3. middle loop:
$$c = forLoopTurn + initThisSum + innerLoopInit + innerLoopCondExtra + branch = \\ 3 + 1 + 2 + 8 = 14$$

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