Beware the Bermuda Triangle
Some gym teachers punish misbehaving students by making them run 50 meters. However, the way in which they must do it is to run 1 meter, then come back, then run 2 meters, then come back, ...
How many total meters does a student run?
∑i=1n i = n * (n + 1) / 2 = O(n2)
for ( i = 0; i < n; i++ ) for ( j = 0; j <= i; j++ ) sum += a[i][j];
Rule: If a computation of O(i) is inside a loop where i is growing up to n, the total computation is O(n2).