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