# 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^{2})

```
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^{2})

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^{2})

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