Snippets Computer Science / Big O

Big O

By Marcelo Fernandes Jul 09, 2017


Big O is a notation that is largely used in Computer Science to describe the performance or complexity of an algorithm.
Big O specifically describes the worst-case scenario, and can be used in order to describe the execution time required or the space used by an algorithm.



0(1) Describes an algorithm that always execute in the same time, 
regardless the size of the input data set. def is_first_element_str(elements): return type(elements[0]) == str

0(n) Describes an algorithm whose performance will grow linearly and
directly proportional to the size of the input data set. Remember: It will always
consider the worst case scenario, which means that if our code has
a for loop that iterates over a list,
even if the loop breaks because of some condition, the big O notation considers that
the worst case scenario is this loop being iterated till the last element.
def is_there_a_string(elements):
    for element in elements:
        if type(element) == str:
            return True
    return False

0(n2) Happens when there are nested iterations over the input.
Deeper iterations will result in 0(n3), 0(n4) ...
def is_there_duplicates(elements):
    for element in elements:
        for compare_element in elements:
            # Pass Self
            if id(element) == id(compare_element):
                if element == compare_element:
                    return True
    return False



1 - Wikipedia.
2 - Rob Bell.