minte9 LearnRemember

Reading / 1 step

A computer can jump to any memory address in one step.
``````
data = ['apples', 'bananas', 'oranges']

item = data[index] # Reading takes 1 step

print('Found item =', item)
print("Steps =", 1)

"""
Found item = bananas
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)

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

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('') # add element at the end of array

steps = 0
for i in range(len(data), key+1, -1): # shift the elements to the right
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)

"""
['apples', 'bananas', 'oranges']
['apples', 'apples', 'bananas', 'oranges']
['cherries', 'apples', 'bananas', 'oranges']
N = 3
Steps = 4
"""
``````

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): # shift elements to left (down to key)
data[i] = data[i+1]
steps += 1

data.pop() # remove last element
steps += 1

return steps

data = ['apples', 'bananas', 'oranges']
size = len(data)
steps = delete_item(data, 0)

print(data)
print('N =', size)
print('Steps =', steps)

"""
['bananas', 'oranges']
N = 3
Steps = 3
"""
``````

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.
``````
steps = 0

# Check for duplicates
for item in data:
steps += 1
if item == new_value:
return -1

# Add new value to the set (random location in the set)
steps += 1

return steps

data = {'apples', 'bananas', 'oranges', 'cherries'}
steps = add_item(data, 'mangos')

print(data)
print('Steps =', steps, '\n')

"""
{'oranges', 'mangos', 'bananas', 'apples', 'cherries'}
Steps = 5
"""
``````

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)

"""
Found: 6 Steps = 4
Found: 16 Steps = 5
Found: 70000 Steps = 16
"""
``````

Last update: 185 days ago