# T(n) = 3n² + 7n + 42
# Dominant term: n²
# Therefore: O(n²)

# T(n) = 5·log(n) + 1000
# Dominant term: log(n)
# Therefore: O(log n)

# Single loop: O(n)
for i in range(n):
    do_something()  # O(1) work per iteration → n × O(1) = O(n)

# Nested loops: O(n²)
for i in range(n):
    for j in range(n):
        do_something()  # n × n × O(1) = O(n²)

# Nested but dependent: still O(n²)
for i in range(n):
    for j in range(i):     # j runs 0, 1, 2, ..., n-1 times
        do_something()     # Total: 0+1+2+...+(n-1) = n(n-1)/2 = O(n²)

# Binary search: halves the search space each iteration
def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:          # Loop runs log₂(n) times
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1       # Halve the space
        else:
            high = mid - 1      # Halve the space
    return -1

# O(1) space — sorts in place
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]

# O(n) space — creates new arrays
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # New array
    right = merge_sort(arr[mid:])   # New array
    return merge(left, right)       # New merged array

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]
    return quicksort(left) + [pivot] + quicksort(right)

# Python list doubles capacity when full
# Most appends are O(1), but resizing copies n elements = O(n)
# Over n appends: total work = n + n/2 + n/4 + ... ≈ 2n
# Amortised cost per append: O(2n/n) = O(1)

import time

def measure(func, *args, repeats=5):
    """Measure average execution time."""
    times = []
    for _ in range(repeats):
        start = time.perf_counter()
        func(*args)
        times.append(time.perf_counter() - start)
    print(f"{func.__name__}: {sum(times)/len(times):.6f}s avg")

def empirical_complexity(func, sizes):
    """Run at different sizes; observe ratio when n doubles."""
    prev_time = None
    for n in sizes:
        data = list(range(n))
        start = time.perf_counter()
        func(data)
        elapsed = time.perf_counter() - start
        ratio = f"{elapsed / prev_time:.1f}x" if prev_time else "-"
        print(f"n={n:>8}  time={elapsed:.4f}s  ratio={ratio}")
        prev_time = elapsed

# If ratio ≈ 2 when n doubles → O(n)
# If ratio ≈ 4 when n doubles → O(n²)
# If ratio ≈ 8 when n doubles → O(n³)

# Shrinking by half → O(log n)
i = n
while i > 0:
    i = i // 2

# Nested loops → O(n²)
for i in range(n):
    for j in range(n):
        pass

# Dependent inner loop → still O(n²): sum 0+1+2+...+(n-1) = n(n-1)/2
for i in range(n):
    for j in range(i):
        pass

# Harmonic series → O(n log n)
for i in range(1, n + 1):
    for j in range(0, n, i):  # n/i iterations per outer loop
        pass

# Two pointers → O(n): each pointer moves at most n times total
left, right = 0, n - 1
while left < right:
    left += 1  # or right -= 1