Time Complexity Comparison

comparing functions in here has new symbols:

  1. :
  2. :
  3. : =
  4. :
  5. :

Definition for :

  • we can write the same thing for .
  • in order to prove is not greater than we need to prove
    that for all the , we have .

Definition for :

Definition for :

or we can write this instead:

Definition for :

session 2