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 O Name
O(1)O(1) constant/bounded time
O(logā€…ā€Šn)O(log \; n) log time
O(n)O(n) linear time
O(nā€…ā€Šlogā€…ā€Šn)O(n \; log \; n) nā€…ā€Šlogā€…ā€Šnn \; log \; n time
O(n2)O(n^2) quadratic/exponential time
O(2n)O(2^n) exponential time
O(n!)O(n!) factorial time

Computer Science Algorithm