Question

To show the worst case complexity in term of the number of addition and comparison of the algorithm.

Short answer

The algorithm then makes \(n - 1\) addition and \(n - 1\) comparisons. \(n - 1 + n - 1 = 2n - 2\), thus, in total \(2n - 2\) additions and comparisons are made while \(2n - 2\) is \(O(n)\).

Step-by-step solution

Given data

The worst case complexity in term of the number of addition and comparison of the algorithm

Concept used of recurrence relation

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms (Expressing\({F_n}\)as some combination of\({F_i}\)with\(i < n)\).

Solve for case complexity

Finally, the algorithm 1 addition and 1 comparison is made every time

\(M(k) = \max \left( {M(k - 1) + {a_k},{a_k}} \right)\)is executed.

Since the for-loop is from 2 to \(n\), the for-loop is executed \(n - 1\) times and thus max \(M(k) = \max \left( {M(k - 1) + {a_k},{a_k}} \right)\) is executed n-1 times.

The algorithm then makes \(n - 1\) addition and \(n - 1\) comparisons. \(n - 1 + n - 1 = 2n - 2\), thus, in total \(2n - 2\) additions and comparisons are made while \(2n - 2\) is \(O(n)\).