def constant_time_example():
my_list = [10, 20, 30, 40, 50]
return my_list[2] # Always takes the same time regardless of list size
def logarithmic_time_example():
# O(log n) - Binary search in a sorted list
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
sorted_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
return binary_search(sorted_list, 5) # Takes logarithmic time
def linear_time_example():
# O(n) - Finding the maximum element in a list
my_list = [1, 3, 5, 7, 9]
max_value = my_list[0]
for num in my_list:
if num > max_value:
max_value = num
return max_value # Takes time proportional to the size of the list
def quadratic_time_example():
# O(n²) - Bubble sort algorithm
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
unsorted_list = [5, 3, 8, 6, 2]
return bubble_sort(unsorted_list) # Takes time proportional to the square of the size of the list
# Execute the examples
print("O(1) Example:", constant_time_example())
print("O(log n) Example:", logarithmic_time_example())
print("O(n) Example:", linear_time_example())
print("O(n²) Example:", quadratic_time_example())