Quiz Corrections, Big O Notation
Quiz Corrections
I only got question 21 wrong. One of my answers was to sort by subject, then sort by year, then filter by photographer. This, however, is incorrect. This sequence of steps does not remove any entries with an unknown year, so the entry in the first row of the spreadsheet will have a year value of -1. The correct answer was to sort by year, then filter by year, then filter by photographer. This option is correct, because sorting by year will sort the spreadsheet on column C from least to greatest. Filtering by year will remove any entries with unknown years. Filtering by photographer will remove any entries with unknown photographers. Since the order of the entries is not affected by the filters, the photograph with the lowest year value will be in the first row of the spreadsheet.
def print_first_element(my_list):
print(my_list[0])
print_first_element([1, 2, 3, 4, 5])
# No matter how big the list is, the time complexity of the code will not change, as finding the first element is easiest with all lists.
def print_all_elements(my_list):
for element in my_list:
print(element)
print_all_elements([1, 2, 3, 4, 5])
# O(n), where n is the amount of elements, shows how as the list grows, so does the time complexity,
# proportionate to each other
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(10))
# Demonstrated here is O(2^n), where n is the number of elements traversed. As n grows, so does the amount
# of time it takes to traverse through the necessary elements of lists created to calculate the return
# value.
def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1
arr = [1, 3, 5, 7, 9]
x = 5
result = binary_search(arr, 0, len(arr)-1, x)
if result != -1:
print(f"Element is present at index {result}")
else:
print("Element is not present in array")
# O(log(n)) is demonstrated here, as where n is the amount of elements traversed, the time it takes divides
# into two, as the searching also does. The recursive search divides into a smaller and smaller task until
# there is only one return value possible.