Big O Notation

O(1) – Constant Time

Example: Accessing an array element by index.

def get_first_element(arr):
    return arr[0]  # Always takes the same time, regardless of array size.

O(log n) – Logarithmic Time

Example: Binary search in a sorted array.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

O(n) – Linear Time

Example: Finding the max value in an unsorted list.

def find_max(arr):
    max_val = arr[0]
    for num in arr:  # Must check every element once.
        if num > max_val:
            max_val = num
    return max_val

O(n²) – Quadratic Time

Example: Bubble sort.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # Swap