cs315 p. 20

Big O from Code

It is often easy to determine Big O directly from code:

Elementary operations such as + or = are O(1).
The Big O for a sequence of statements is the max of the Big O of the statements.
The Big O for an if statement is the max of the Big O of the test, then statement, and else statement.
The Big O for a loop is the loop count times the Big O of the contents.
Big O for a recursive call that cuts the problem size in half is log(n).


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

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


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