Big O from Code

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

• Elementary ops such as +, =, a[i], v.f 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:
  • discard one half: log(n) (binary search).
  • process both halves: n · log(n) (quicksort).