## Problem:

Give the big-o notation for the following:

for (i=0; i<n; i++) { for (j=0, sum=a[0]; j=i; j++) { sum += a[j]; } }

## Solution:

At first glance, this algorithm appears to be running in quadratic time because of the two nested for loops. However, it requires further analysis because the second loop increments to i each time, rather than n.

Second loop has a run-time of: 1 + 2 + 3 + ... + n = n(n+1) / 2

Since the first 'for' loop has already been taken into account in solving the inner loop's equation above, I believe that the total run-time is also: n(n+1) / 2

## Conclusion:

The algorithm's max run-time is in fact: O(n2)