big_o.py

# Big O notation is "worst case" time of an algorithm:
#  - O is used as a function
#  - n the input (mostly assumed to be an integer)
#  - any transformations done to n (say 2n) are representative of the operations inside the algorithm
#
# so take the following:

def count_to_n(n):
  "count up to n (obviously contrived)"
  # do some preparation work
  call_the_other_thing()
  
  # now count!
  for i in range(n):
    print n
    
# Counting the operations inside the function (one for call_the_other_thing, n times printing), we get O(n+1)
# Typically we'd drop the constant and ignore the runtime of whatever happens in other functions, so we get O(n)
# (this is also known as "linear time", since the constant you pass in is directly correlated to running time)

# now we'll modify:

def count_to_n_twice(n):
  "count up to n (obviously contrived)"
  # do some preparation work
  call_the_other_thing()
  
  # now count!
  for i in range(n):
    print "previously:", n - 1
    print n
    
# now the runtime is O(2n+1) or O(2n). We do two operations for every iteration of n.