Big O Notation - Exercises
1 min read

# 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(N2)

``````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(N2)

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(N2)

```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))