Click to Flip Card

### Time Complexity

What is time complexity, or big O notation? Is big O focusing on the runtime? Which one is faster, O(N) or O(log N)?

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

Last update: 185 days ago