Skip to content

1.6 Class of functions

function
O(1) constant
O(logn) logarithmic
O(n) linear
n^2 Quadratic
n^3 cubic
O(2^n) exponential

1.7 Compare Class of functions

$$ 1 < log (n) < \sqrt n < n < nlog(n) < n^2 < n^3 ... 2^n < 3^n ... n^n $$

functions express the complexity as n increases

1.8 Asymptotic Notations

$$ O() : big-oh : upper bound $$

$$ \Omega : big-omega : lower bound $$

$$ \Theta : Theta : Average bound $$

1.11 Best, worst, and average case analysis

  • best case : searching key element present at first index
  • O(1)
  • Worst case : searching key at last index
  • O(n)
  • Average case : (all possible cast time) / number of cases
  • O(n)
  • best case : searching key element present at first index
  • O(1)
  • Worst case : searching key at last index
  • min = O(log n), max = O(n)
  • Average case : (all possible cast time) / number of cases
  • O(log n)