Tuesday, April 11, 2017

Big O notation

  • Big O notation is the language we use for articulating how long an algorithm takes to run. It's how we compare the efficiency of different approaches to a problem.
  • With big O notation we express the runtime in terms of—brace yourself—how quickly it grows relative to the input, as the input gets arbitrarily large.

More examples of Big O
O(1)          : Static
O(log n)     : Divide and conquer. Ex: ( Binary search )
O(n )          : Directly and linearly related to n
O(n log n ) : Merge search : deck of cards
O(n2)         : Checking list + grocery cart
O(infinity ):  Tossing a coin

No comments:

Post a Comment