Main Complexity Table

1.  O(1)  Constant Time - Example:  Determining if an           integer (represented in binary) is odd or even, swap

2.  O(lgn)  Logarithmic Time - Example:  binary search

3.  O(n)  Linear Time - Example:  linear search, find min,       find max

4.  O(nlgn)  Quasilinear Time - Example:  merge sort,           quick sort

5.  O(n^2)  Quadratic Time - Example:  standard bubble       sort, worst case insertion sort, selection sort worst         and best case

6.  O(2^n)  Exponential Time - Example: subset sum,           recursive algorithms

9.  O(n!)  Factorial Time - Example:  Solving the                     traveling salesman problem via brute-force search,       factorial problem

7.  2^O(logn) = poly(n)  Polynomial Time - Example:  A        Non-Deterministic Turing Machine that runs in                Polynomial Time, calculating the greatest common        divisor     

8.  NPC Non-Deterministic Polynomial Time Complete -         Exponential Time - Example:  Hamiltonian Path                     problem, knapsack problem