Time Complexity Examples Notebook
This notebook demonstrates examples of functions with the following time complexities:
- O(1)
- O(log n)
- O(n)
- O(n²)
O(1) — Constant Time
def get_first_element(arr):
# Accessing the first element takes constant time
return arr[0]
O(log n) — Logarithmic Time
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return True
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return False
# Example: Must pass a sorted array!
binary_search([1, 3, 5, 7, 9, 11], 7)
O(n) — Linear Time
def find_max(arr):
max_val = arr[0]
for item in arr:
if item > max_val:
max_val = item
return max_val
O(n²) — Quadratic Time
def has_duplicates(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] == arr[j]:
return True
return False