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)
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)
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
data = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
data, steps = bubble_sort(data)
print(data)
print("Steps =", steps)
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)