Contents    Page-10    Prev    Next    Page+10    Index   

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++ )      ; i up to n times
  for ( j = 0; j <= i; j++ )   ; O(i)
    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).