Big O Notation - Exercises

This page features some exercises to better understand the big O notation. Try to figure out what each algorithm's complexity is. To verify, hover the blacked-out text under each algorithm to reveal the answer.
Good luck!

def func(N:int):
    s = 0
    for i in range(N):
        s += 1

Answer:

O(N)

def func(N:int):
    s = N*N
    print(s)

Answer:

O(1)

def func(N:int):
    s = 0
    for i in range(N):
        s += 1
    for i in range(N):
        s += 1

Answer:

O(N)

def func(N:int):
    s = 0
    for i in range(N):
        for i in range(N):
            s += 1

Answer:

O(N²)

def func(N:int, I:int):
    for i in range(N):
        s = 0
        while s<I:
            s += 1

Answer:

O(NI)

def func(N:int):
    s = 0
    for i in range(N):
        for i in range(N):
            s += 1
        for i in range(N):
            print(f"added {i}")
            s += i

Answer:

O(N²)

Let's finish with two real algorithms :

def insertion_sort(array:list):
    i, j = 1, 0
    
    while i < len(array):
        m_i, m_j = i, j
        while (array[i] < array[j]) and j >= 0:
            array[i], array[j] = array[j], array[i]
            i -= 1
            j -= 1
        i = m_i + 1
        j = m_j + 1

Answer:

O(N²)

def binary_search(array:list, value:int):
    half = len(array)//2
    if array[half] != value and len(array) > 1:
        if array[half] > value:
            return binary_search(array[:half], value)
        else:
            return binary_search(array[half:], value)
    elif array[half] == value:
        return True
    return False

Answer:

O(log(N))