big o notation python

def print_all_numbers_then_all_pair_sums(list_of_numbers):

    print "these are the numbers:"
    for number in list_of_numbers:  #here n is the big o notation
        print number

    print "and these are their sums:"
    for first_number in list_of_numbers:     # here n^2 is the big o notation
        for second_number in list_of_numbers:
            print first_number + second_number


#Here our runtime is O(n + n^2)   which we call O(n^2).Even if it was O(n^2 + 100n), it would still be O(n^2).

talking about worst case:
 source :://www.interviewcake.com/article/python/big-o-notation-time-and-space-complexity
def contains(haystack,needle):
 #does the haystack contain the needle?
for item in haystacK:
  if item==needle:
return True
return False
here we might have 100 items  in our haystack , but the first item might be the needle , in which case we would return in just 1 iteration of our loop
in general way we'd say this is O(n) runtime and the worst case parrt would be implied.But to be more specific we could say  this is worst case O(n) and the best case O(1) rutime. For some algorithms we can also make rigorous statements about the "average case" runtime


space complexity: the final frontier:
sometimes we want to optimize for using less memory instead of ( or in addition) using less time.Talking about the memory cost ( or "space complexity") is very similiar to talking about time cost. We simply look at the total size ( relative to the size of the input) of any new variables we are allocating
 the function takes 0(1) space ( we aren't allocating any new variable)

def say_hi_n_times(n):
for time in range(n):
print "hi"

the function takes O(n) space(the size of hi_list scales with the size of the input):

now the following function takes O(n) space ( the size of the hi_list scales with the size of the input):
def list_of_hi_n_times(n):
hi_list=[]

for time in range(n):
hi.list.append('hi')
return hi_list
usually when we talk about space complexity we are talking about additional space:

we dont include space taken up by the inputs.For eg: this function takes constant space even though the input has n items:

def get_largest_item(list_of_items):
largest=0
for item i list_of_items:
if item > largest:
return largest



Big O anaylis is awesome except when it is not

You should make a habit of thinking about the time and space complexibility  of algorithms as you design them. Before long this'll become second nature ,allowing you to see optimizations and potential performances issues right away



source :://www.interviewcake.com/article/python/big-o-notation-time-and-space-complexity