Reading lists - O(1)
""" READING LISTS - O(1)
------------------------
Accessing an item by list index takes a constant time: 1 step.
The computer "jumps" directly to the memory address of that index (number).
It's like opening a book to a specific page using a bookmark.
Time complexity is O(1)
-----------------------
"""
data = ["apples", "bananas", "oranges"]
index = 1
item = data[index] # Reading takes 1 step -> O(1)
print("Found item=", item) # bananas
print("Steps =", 1) # 1
Searching lists - O(n)
""" SEARCHING LISTS - O(n)
--------------------------
Linear search from a list takes maximum n steps.
Check each item one by one until you find the target (or reach the end).
In the worst case, you look at every element - N steps for N items.
It's like looking for "oranges" in a grocery receipt by
reading each line from top to bottom.
Time complexity:
- Worst case: O(N) - last item matched
- Best case: O(1) - first item matched
When to use:
- The list is unsorted.
- Simplicity is preferred over performance.
- The list is small, so the overhead is negligible.
---------------------------------------------------
"""
fruits = ["apples", "bananas", "oranges"]
def search_value(items, value):
for i in range(len(items)):
if value == items[i]:
return i # Found, return index
return -1
item = "oranges"
index = search_value(fruits, item)
print(f"Found {item} at index {index}, steps = {index + 1}") # O(N)
item = "apples"
index = search_value(fruits, item)
print(f"Found {item} at index {index}, steps = {index + 1}") # O(1)
# -----------------------------------
# Found oranges at index 2, steps = 3
# Found apples at index 0, steps = 1
Inserting lists - O(n)
""" INSERT LISTS - O(n)
-----------------------
Inserting into a specific index in a list takes maximum n steps.
To insert at position key, we first make space by shifting all elements
from the right toward the end, then place the new value.
Why N+1 steps?
- Up to N shifts (to move items and make space)
- +1 step to write teh new value into position
Real-life analogy:
In a row of theater seats, to seat a new person in the middle,
everyone to the right has to move over one seat.
Time complexity:
O(N) - shifts grow with the number of elements to the right of key.
When to use:
When order matters and you must insert at a specific position.
----------------------------------------------------------------
"""
fruits = ["apples", "bananas", "oranges"]
def add(data, k, value):
steps = 0
# Create new list to avoid list being changed in place (lists are mutable)
items = data[:]
# add one empty element at the end
items.append("")
# from end down to the k+1
for i in range(len(items), k+1, -1): # start, stop (required), step
items[i-1] = items[i-2] # shift elements one position to the right
steps += 1
# place the new value in the gap
items[k] = value
steps += 1
return items, steps
res, steps = add(fruits, 1, "kiwi")
print(res, steps)
res, steps = add(fruits, 2, "kiwi")
print(res, steps)
assert add(fruits, 1, "kiwi") == (['apples', 'kiwi', 'bananas', 'oranges'], 3)
assert add(fruits, 2, "lemons") == (['apples', 'bananas', 'lemons', 'oranges'], 2)
# -------------------------------------------
# ['apples', 'kiwi', 'bananas', 'oranges'], 3
# ['apples', 'bananas', 'kiwi', 'oranges'], 2
Deleting lists - O(n)
""" DELETING LISTS - O(n)
-------------------------
Deleteing from a list at a specific index takes maximum n steps.
To remove the item at key, we shift everything to its right one step left
to cover the gap, then remove the non-duplicate last element.
Why N+1 steps?
- Up to N-1 shifts (elements to the right of the `key`)
- +1 step to pop() the trailing duplicate
Real-life analogy:
Pull a book from the middle of a tight shelf: every book to the right
slides left by one position to close the gap, then you tidy the end.
Time complexity:
O(N) - proportional to how many elements are to the right of `key`
Note:
This function MUTATES the input list.
---------------------------------------
"""
fruits = ["apples", "bananas", "oranges"]
def delete_item(data, k):
steps = 0
for i in range(k, len(data)-1): # start at specific index
data[i] = data[i+1]
steps += 1
data.pop() # remove the duplicate last element
steps += 1
return steps
delete_item(fruits, 1)
print(fruits)
# -----------------------
# ['apples', 'oranges']
