Reading / 1 step
A computer can jump to any memory address in
one step.
data = ['apples', 'bananas', 'oranges']
item = data[index]
print('Found item =', item)
print("Steps =", 1)
Searching / N steps
For N cells in an array, linear search would take a maximum of
N steps.
def search_value(arr, value):
steps = 0
for i in range(len(arr)):
steps += 1
if value == arr[i]:
return i, steps
return -1, steps
data = ['apples', 'bananas', 'oranges']
key, steps = search_value(data, 'oranges')
print('Found at index =', key)
print('N =', len(data))
print('Steps =', steps)
Insertion / N+1 steps
We need to
shift items in order to make room for the new item.
def add_item(data, new_value, key):
data.append('')
steps = 0
for i in range(len(data), key+1, -1):
data[i-1] = data[i-2]
steps += 1
print(data)
data[key] = new_value
steps += 1
return steps
data = ['apples', 'bananas', 'oranges']
print(data)
size = len(data)
steps = add_item(data, 'cherries', 0)
print(data)
print('N =', size)
print('Steps =', steps)
Deletion / N+1 steps
To delete an item require one step, then N-1 step for
shifting the rest of elements.
def delete_item(data, key):
steps = 0
for i in range(key, len(data)-1):
data[i] = data[i+1]
steps += 1
data.pop()
steps += 1
return steps
data = ['apples', 'bananas', 'oranges']
size = len(data)
steps = delete_item(data, 0)
print(data)
print('N =', size)
print('Steps =', steps)
Set / Insertion
A set is a data structure of unordered elements that doesn't allow
duplicates.
In terms of time compexity, the only
difference between arrays and sets is at insertion.
def add_item(data, new_value):
steps = 0
for item in data:
steps += 1
if item == new_value:
return -1
data.add(new_value)
steps += 1
return steps
data = {'apples', 'bananas', 'oranges', 'cherries'}
steps = add_item(data, 'mangos')
print(data)
print('Steps =', steps, '\n')
Ordered / Binary Search
When inserting we need to make a
search before in order to get the correct spot.
While insertion is less efficient for an ordered array, the search is match
more efficient.
def binary_seach(arr, val):
left = 0
right = len(arr) - 1
steps = 0
while True:
steps += 1
middle = (left + right) // 2
if val == arr[middle]:
return middle, steps
if val > arr[middle]:
left = middle + 1
if val < arr[middle]:
right = middle - 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("Found:", key, end=' ')
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("Found:", key, end=' ')
print("Steps =", steps)
data = [i for i in range(0, 100_100)]
key, steps = binary_seach(data, 70_000)
print("Found:", key, end=' ')
print("Steps =", steps)