Big O

  • Expresses computing time as the term in a function that increases most rapidly to the size of a problem
  • How fast an algorithm is
    • Rate of growth of operations
    • How the running time will increase as the input increases
  • Worst-case run time
  • Can we do better?

Common Run Times

  • Fastest --> slowest
Big OName
$O(1)$constant/bounded time
$O(log ; n)$log time
$O(n)$linear time
$O(n ; log ; n)$$n ; log ; n$ time
$O(n^2)$quadratic/exponential time
$O(2^n)$exponential time
$O(n!)$factorial time

Computer Science Algorithm