Big O examples

O(n)

def find_sum(items):
    sum = 0

    for item in items
        sum += item

    return sum

def find_max(items):
    max = 0

    for item in items:
        if item > max:
          max = item

    return max

O(1)

doesn’t exist any iteraction

def hello_world():
    print('hello world')

def return_the_same(n):
    return n

def first(items):
    return items[0]

def increase_queue():
    the_queue = queue.Queue()
    the_queue.put(2)

O(n²)

def find_common_elements(items1, items2):
    result = []

    for item1 in items1:
        for item2 in items2:
            if item1 == item2:
                result.append(item1)

    return result

O(2ⁿ)

solve with 2 sub-problems

def fibonacci(num):
    if num <= 1:
        return num

    return fibonacci(n - 2) + fibonacci(n - 1)

O(n!)

def factorial(n):
    for x in xrange(n):
        print x
        factorial(n - 1)