Big O

  • 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(logā€…ā€Šn)O(log \; n) log time
O(n)O(n) linear time
O(nā€…ā€Šlogā€…ā€Šn)O(n \; log \; n)
O(n2)O(n^2) exponential time
O(n!)O(n!) factorial time

Computer Science Algorithm