Time Complexity

Time Complexity Examples

This notebook has the Python examples for different time complexities:

• O(1): Constant Time
• O(log n): Logarithmic Time
• O(n): Linear Time
• O(n²): Quadratic Time

# O(1) - Constant Time
def get_first_element(arr):
    return arr[0]  # Accessing the first element takes constant time

get_first_element([5, 10, 15, 20])

# O(log n) - Logarithmic Time (Binary Search)
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

binary_search([1, 3, 5, 7, 9, 11, 13], 7)

# O(n) - Linear Time
def linear_search(arr, target):
    for i in arr:
        if i == target:
            return True
    return False

linear_search([1, 2, 3, 4, 5], 4)

# O(n^2) - Quadratic Time (Nested Loops)
def print_all_pairs(arr):
    for i in arr:
        for j in arr:
            print(f"({i}, {j})")

print_all_pairs([1, 2, 3])