# 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}$$