Snippets Computer Science / Big O

Big O

By Marcelo Fernandes Jul 09, 2017

Definition:

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.

Examples:

O(1)

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
O(n)

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
            
        
O(n2)

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):
                pass
            else:
                if element == compare_element:
                    return True
    return False
            
        

Notes


References:


1 - Wikipedia.
2 - Rob Bell.