def linear_search(arr, target):
    for i in range(len(arr)):   # runs at most n times
        if arr[i] == target:
            return i            # could return early (best case O(1))
    return -1

# Worst case: target not found → O(n)
# Best case:  target is arr[0]  → O(1)
# Both are valid Big O statements about DIFFERENT scenarios

def find_min(arr):
    min_val = arr[0]
    for x in arr:        # must look at every element
        if x < min_val:
            min_val = x
    return min_val

# T(n) = Ω(n)  — you MUST examine all n elements
# No shortcut exists without extra structure like a sorted array

def sum_array(arr):
    total = 0
    for x in arr:   # exactly n iterations, always
        total += x
    return total

# Every call touches exactly n elements.
# T(n) = Θ(n)  — tight bound (not O(1), not O(n²))

# Merge sort:
# Best case:    O(n log n)
# Worst case:   O(n log n)
# Average case: O(n log n)
# → T(n) = Θ(n log n)  because best == worst (same order)

def example(arr):
    n = len(arr)

    result = 0              # O(1)

    for x in arr:           # O(n)
        result += x

    for i in range(n):      # O(n²) — nested loop
        for j in range(n):
            result += arr[i] * arr[j]

    return result

# Dominant term: n²
# T(n) = O(n²)  — the O(n) and O(1) parts are absorbed

# Full breakdown: c1 + c2*n + c3*n² = O(n²)

# Both are O(n) — constant factors are absorbed:
def fast_scan(arr):
    return sum(arr)          # ~1 operation per element

def slow_scan(arr):
    total = 0
    for x in arr:
        for _ in range(1000):   # constant inner loop
            total += x / 1000
    return total

# At n = 1,000,000:
# fast_scan: ~1,000,000 ops
# slow_scan: ~1,000,000,000 ops
# 1000x difference, BUT both are O(n).
# In practice constants matter — Big O tells you the category.

def print_grid(rows, cols):
    for r in range(rows):      # 'rows' iterations
        for c in range(cols):  # 'cols' iterations
            print(r, c)

# T = O(rows × cols)  — cannot simplify to O(n²) unless rows == cols

# BFS/DFS on a graph:
# T = O(V + E)
# V = number of vertices, E = number of edges
# These are independent variables — both stay in the notation

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):          # O(n) — one pass
        complement = target - num
        if complement in seen:              # O(1) — hash lookup
            return [seen[complement], i]
        seen[num] = i                       # O(1) — hash insert
    return []

# Time complexity:  O(n) — one loop, constant-time ops inside
# Space complexity: O(n) — hash map stores up to n entries
#
# Is this optimal?
# Lower bound: Ω(n) — must read all elements at least once
# Upper bound: O(n) — our algorithm achieves this
# → Θ(n) tight bound. This solution is asymptotically optimal!