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