Some gym teachers punish misbehaving students by making them run 50 yards. However, the way in which they must do it is to run 1 yard, then come back, then run 2 yards, then come back, ...

How many total yards does a student run?

*&sum _{i=1}^{n} i = n * (n + 1) / 2 = O(n^{2}) *

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(n ^{2})*.