Contents    Page-10    Prev    Next    Page+10    Index   

Big O of Loops


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

We all know this is O(n2); but what about:


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