# minte9 LearnRemember

### BigO Notation

Compute scientists have borrowed the concept from mathematics. Big O is focusing on the number of steps, but in a specific way.

### Linear Search / O(n)

Linear search will take as many steps as the number of elements in the array. The algorithm's time complexity is called linear.
`````` def linear_search(arr, x):
steps = 0
for i in range(len(arr)):
steps += 1
if x == arr[i]:
return i, steps
return -1, steps

data = ['apples', 'bananas', 'oranges']
key, steps = linear_search(data, 'oranges')

print('Found at index =', key)
print('N =', len(data))
print('Steps =', steps)

"""
Found at index = 2
N = 3
Steps = 3
"""
``````

### Binary Search / O(log n)

For n elements the algorithm increases one step each time the data is doubled. The algorithm's time complexity is logarithmic.
`````` def binary_seach(arr, x):
left = 0
right = len(arr) - 1

steps = 0
while True:

steps += 1
m = (left + right) // 2

if x == arr[m]:
return m, steps

if x > arr[m]: left = m + 1
if x < arr[m]: right = m - 1

if left > right:
return -1, steps

data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
key, steps = binary_seach(data, 7)
print("Steps =", steps)

data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
key, steps = binary_seach(data, 17)
print("Steps =", steps)

"""
Steps = 4
Steps = 5
"""
``````

### Bubble Sort / O(n^2)

The algorithm keep track of the rightmost index of the array that has not yet been sorted. As the number increases, the number of steps grows exponentialy.
`````` def bubble_sort(arr):
right = len(arr) - 1
sorted = False
steps = 0

while not sorted:
sorted = True

for i in range(right):
steps += 1

if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
steps += 1

sorted = False
right -= 1
return arr, steps

# Bubble Sort steps
data = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
data, steps = bubble_sort(data)
print(data)
print("Steps =", steps)

# Side by side comparition
print("n \t Bubble sort steps \t n^2")
for n in [5, 10, 20, 40, 80]:
arr = [i for i in range(n, 0, -1)]

_, steps = bubble_sort(arr)
print(n, '\t', steps, '\t\t\t', n**2)

"""
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Steps = 90

n      Bubble sort steps      n^2
5      20                  25
10      90                  100
20      380                  400
40      1560                  1600
80      6320                  6400
"""
``````