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)