Big O Notation Homework
- ✅ O(1) – Constant Time
- ✅ O(log n) – Logarithmic Time (Binary Search)
- ✅ O(n) – Linear Time
- ✅ O(n²) – Quadratic Time
✅ O(1) – Constant Time
def get_first_element(arr):
return arr[0] # Always takes same time regardless of size
✅ O(log n) – Logarithmic Time (Binary Search)
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return True
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return False
✅ O(n) – Linear Time
def sum_list(arr):
total = 0
for num in arr:
total += num
return total
✅ O(n²) – Quadratic Time
def has_duplicate_pair(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] == arr[j]:
return True
return False