Time Complexity

# =============================================================================
#File name: 01_big_o_demo.py
#Description: Visualize the main Big-O complexity classes with the actual number of operations
#Time Complexity: See comments for each function
#Space Complexity: O(1) — No additional space used
# =============================================================================

import math


# ---------------------------------------------------------------------------
#O(1) — Constant time: Always the same number of operations regardless of input size
# ---------------------------------------------------------------------------
def o_constant(arr: list) -> tuple:
    """Returns the first element of the array. Time complexity: O(1)"""
    count = 0
    result = arr[0]  #Only one access
    count += 1
    return result, count


# ---------------------------------------------------------------------------
#O(log n) — Logarithmic time: Halve the search range at each step
# ---------------------------------------------------------------------------
def o_log_n(n: int) -> int:
    """Returns the number of steps to reach 1 using the binary search method. Time complexity: O(log n)"""
    count = 0
    current = n
    while current > 1:
        current //= 2  #Halve it
        count += 1
    return count


# ---------------------------------------------------------------------------
#O(n) — Linear time: Visit each element of the array once
# ---------------------------------------------------------------------------
def o_linear(arr: list) -> tuple:
    """Calculates the sum of an array. Time complexity: O(n)"""
    count = 0
    total = 0
    for x in arr:  #Repeat n times
        total += x
        count += 1
    return total, count


# ---------------------------------------------------------------------------
#O(n log n) — Linearithmic time: Perform log steps for each element
# ---------------------------------------------------------------------------
def o_n_log_n_estimate(n: int) -> int:
    """Returns the expected number of operations for n log n. Time complexity: O(n log n)"""
    if n <= 1:
        return 1
    return int(n * math.log2(n))


# ---------------------------------------------------------------------------
#O(n²) — Quadratic time: Nested loops (check all pairs)
# ---------------------------------------------------------------------------
def o_quadratic(arr: list) -> tuple:
    """Count the cases where the sum of all element pairs is 0. Time complexity: O(n²)"""
    count = 0
    pairs = 0
    n = len(arr)
    for i in range(n):              #Outer loop: n times
        for j in range(i + 1, n):  #Inner loop: n-i-1 times
            count += 1
            if arr[i] + arr[j] == 0:
                pairs += 1
    return pairs, count


# ---------------------------------------------------------------------------
#O(2ⁿ) — Exponential time: Enumerate all subsets (only feasible for small n)
# ---------------------------------------------------------------------------
def o_exponential(n: int) -> int:
    """Returns the number of all subsets of n elements. Time complexity: O(2ⁿ)"""
    count = 0
    for mask in range(1 << n):  #2^n cases
        count += 1
    return count


# ---------------------------------------------------------------------------
#Display table comparing growth of complexities
# ---------------------------------------------------------------------------
def print_complexity_table(n: int) -> None:
    """When n is given, the number of operations for each complexity is printed in a table."""
    log_n = int(math.log2(n)) if n > 1 else 1
    n_log_n = int(n * math.log2(n)) if n > 1 else n
    n_sq = n * n
    two_n = 2 ** n if n <= 30 else None

    print(f"Complexity growth comparison (n={n})")
    print("╔═══════════════╦══════════════════════╗")
    print("║ Big-O         ║ Number of Operations (Approx.)        ║")
    print("╠═══════════════╬══════════════════════╣")
    print(f"║ O(1)          ║ {1:<20} ║")
    print(f"║ O(log n)      ║ {log_n:<20} ║")
    print(f"║ O(n)          ║ {n:<20} ║")
    print(f"║ O(n log n)    ║ {n_log_n:<20} ║")
    print(f"║ O(n²)         ║ {n_sq:<20} ║")
    if two_n is None:
        print(f"║ O(2ⁿ)         ║ {'Too large (uncomputable)':<20} ║")
    else:
        print(f"║ O(2ⁿ)         ║ {two_n:<20} ║")
    print("╚═══════════════╩══════════════════════╝")


def main():
    print("=" * 55)
    print("Big-O complexity demo")
    print("=" * 55)

    n = 100_000
    arr_large = list(range(n))

    #O(1) demo
    _, cnt = o_constant(arr_large)
    print(f"O(1)     Number of operations: {cnt:>12}  (n={n})")

    #O(log n) demo
    cnt = o_log_n(n)
    print(f"O(log n) Number of operations: {cnt:>12}  (n={n})")

    #O(n) demo
    _, cnt = o_linear(arr_large)
    print(f"O(n)     Number of operations: {cnt:>12}  (n={n})")

    #O(n log n) demo (expected value)
    cnt = o_n_log_n_estimate(n)
    print(f"O(n logn)Number of operations: {cnt:>12}  (n={n}, expected value)")

    #O(n²) — Measure with a small array
    n_small = 1000
    arr_mid = list(range(-n_small // 2, n_small // 2))
    _, cnt = o_quadratic(arr_mid)
    print(f"O(n²)    Number of operations: {cnt:>12}  (n={n_small})")

    #O(2ⁿ) — Only possible for very small n
    n_exp = 20
    cnt = o_exponential(n_exp)
    print(f"O(2ⁿ)    Number of operations: {cnt:>12}  (n={n_exp})")

    #Table comparing growth of complexities
    print_complexity_table(16)
    print_complexity_table(1000)
    print_complexity_table(1_000_000)

    print("[Note] Time limit 1 second ≈ 10^8 operations")
    print("[Note] If n=100,000, O(n log n) ≈ 1.7×10^6 → safe")
    print("[Note] If n=100,000, O(n²)      ≈ 10^10  → time limit exceeded")


if __name__ == "__main__":
    main()

# =============================================================================
#Filename: 02_time_measure.py
#Description: Compare bubble sort (O(n²)) and built-in sorted() (O(n log n)) using the timeit / time modules
#Time complexity: Bubble sort O(n²), sorted() O(n log n)
#Space complexity: O(n) — array to be sorted
# =============================================================================

import time
import timeit
import random
import copy


# ---------------------------------------------------------------------------
#Bubble sort — O(n²)
# ---------------------------------------------------------------------------
def bubble_sort(arr: list) -> list:
    """Implement bubble sort. Time complexity: O(n²), space complexity: O(1)"""
    a = arr[:]          #Copy to preserve original
    n = len(a)
    for i in range(n):              #Outer loop: n times
        swapped = False
        for j in range(n - i - 1):  #Inner loop: n-i-1 times
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]  #Swap
                swapped = True
        if not swapped:             #Already sorted → Early exit optimization
            break
    return a


# ---------------------------------------------------------------------------
#Insertion sort — O(n²) average, O(n) best
# ---------------------------------------------------------------------------
def insertion_sort(arr: list) -> list:
    """Insertion sort implementation. Time complexity: O(n²) average, space complexity: O(1)"""
    a = arr[:]
    for i in range(1, len(a)):       #From the first to the last element
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:  #Find the appropriate position
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a


# ---------------------------------------------------------------------------
#Time measurement utility
# ---------------------------------------------------------------------------
def measure_time(func, arr: list) -> float:
    """Returns the function execution time in seconds."""
    data = copy.deepcopy(arr)
    start = time.perf_counter()
    func(data)
    return time.perf_counter() - start


def benchmark(sizes: list) -> None:
    """Compares the execution times of sorting algorithms for various input sizes."""
    print("\n" + "=" * 70)
    print("Sorting algorithm performance comparison")
    print("=" * 70)
    header = (
        f"{'Input size':>10}"
        f"{'Bubble sort (sec)':>14}"
        f"{'Insertion sort (sec)':>14}"
        f"{'sorted() (sec)':>14}"
    )
    print(header)
    print("-" * 70)

    for size in sizes:
        random.seed(42)
        arr = [random.randint(1, 10 ** 6) for _ in range(size)]

        t_bubble = measure_time(bubble_sort, arr)
        t_insert = measure_time(insertion_sort, arr)

        #sorted() is Timsort — O(n log n)
        start = time.perf_counter()
        sorted(arr)
        t_sorted = time.perf_counter() - start

        ratio_b = t_bubble / t_sorted if t_sorted > 0 else float('inf')
        ratio_i = t_insert / t_sorted if t_sorted > 0 else float('inf')

        print(
            f"{size:>10,}  "
            f"{t_bubble:>13.6f}s "
            f"{t_insert:>13.6f}s "
            f"{t_sorted:>13.6f}s"
        )
        print(
            f"{'':>10}  "
            f"({ratio_b:>6.1f}x slower)"
            f"({ratio_i:>6.1f}x slower)"
        )

    print("=" * 70)
    print("[Conclusion] O(n²) algorithms get significantly slower as n increases.")
    print("For n=10,000 or more, O(n log n) should be used.")


def main():
    print("timeit module example — measure performance of short code")
    print("-" * 40)

    #Compare list comprehension vs loop with timeit
    t_comp = timeit.timeit(
        '[x**2 for x in range(1000)]',
        number=1000
    )
    t_loop = timeit.timeit(
        stmt=(
            'result = []\n'
            'for x in range(1000):\n'
            '    result.append(x**2)'
        ),
        number=1000
    )
    print(f"List comprehension (1000 times): {t_comp:.4f} sec")
    print(f"for loop + append (1000 times): {t_loop:.4f} seconds")
    if t_comp > 0:
        print(f"Comprehension is {t_loop/t_comp:.2f} times faster")

    #Sorting algorithm benchmark
    benchmark(sizes=[100, 1000, 5000])


if __name__ == "__main__":
    main()

# =============================================================================
#Filename: 03_space_complexity.py
#Description: Measure O(1), O(n), O(n²) space complexity using sys.getsizeof
#Time complexity: O(n²) — when creating a 2D array
#Space complexity: see comments for each function
# =============================================================================

import sys


# ---------------------------------------------------------------------------
#O(1) space — uses only a fixed number of variables
# ---------------------------------------------------------------------------
def sum_o1_space(arr: list) -> int:
    """Sum calculation of an array. Space complexity: O(1) — using only 2 variables"""
    total = 0       #One variable
    for x in arr:   #One loop variable (stack usage ignored)
        total += x
    return total


# ---------------------------------------------------------------------------
#O(n) space — additional space proportional to input size
# ---------------------------------------------------------------------------
def prefix_sum_on_space(arr: list) -> list:
    """Return the cumulative sum array. Space complexity: O(n) — result array of n elements"""
    n = len(arr)
    prefix = [0] * (n + 1)  #n+1 additional spaces
    for i in range(n):
        prefix[i + 1] = prefix[i] + arr[i]
    return prefix


# ---------------------------------------------------------------------------
#O(n²) space — 2D array (n × n)
# ---------------------------------------------------------------------------
def create_matrix_on2_space(n: int) -> list:
    """Create an n×n matrix. Space complexity: O(n²)"""
    matrix = [[0] * n for _ in range(n)]  #n*n spaces
    for i in range(n):
        matrix[i][i] = 1  #Identity matrix form
    return matrix


# ---------------------------------------------------------------------------
#Recursive call stack space — O(n) (equal to the depth of calls)
# ---------------------------------------------------------------------------
def recursive_factorial(n: int) -> int:
    """Recursive factorial. Space complexity: O(n) — call stack depth n"""
    if n <= 1:
        return 1
    return n * recursive_factorial(n - 1)  #n stack frames stacked


def iterative_factorial(n: int) -> int:
    """Iterative factorial. Space complexity: O(1) — no additional space"""
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result


# ---------------------------------------------------------------------------
#Memory usage measurement helper
# ---------------------------------------------------------------------------
def list_total_size(obj: list) -> int:
    """Calculates the total memory usage of the list (header + all elements)."""
    if not isinstance(obj, list):
        return sys.getsizeof(obj)
    total = sys.getsizeof(obj)
    for item in obj:
        total += sys.getsizeof(item)
    return total


def main():
    print("=" * 55)
    print("Demonstration of space complexity")
    print("=" * 55)

    sizes = [10, 100, 1000]

    # -----------------------------------------------------------------------
    #Measure O(1) space
    # -----------------------------------------------------------------------
    print("[O(1) space] Variable usage (independent of input size)")
    for n in sizes:
        print(f"n={n:>5}: uses only 2 additional variables → constant space")

    # -----------------------------------------------------------------------
    #Measure O(n) space
    # -----------------------------------------------------------------------
    print("[O(n) space] Size of cumulative sum array")
    for n in sizes:
        arr = list(range(n))
        prefix = prefix_sum_on_space(arr)
        total_bytes = list_total_size(prefix)
        print(
            f"n={n:>5}: prefix array size ="
            f"{len(prefix):>5},"
            f"Total {total_bytes:>7} bytes"
            f"(≈ {total_bytes/1024:.1f} KB)"
        )

    # -----------------------------------------------------------------------
    #Measure O(n²) space
    # -----------------------------------------------------------------------
    print("[O(n²) space] n×n matrix size")
    for n in [10, 100, 300]:
        matrix = create_matrix_on2_space(n)
        total_bytes = sys.getsizeof(matrix)
        for row in matrix:
            total_bytes += sys.getsizeof(row)
            total_bytes += sum(sys.getsizeof(x) for x in row)
        print(
            f"n={n:>4}: {n}×{n} matrix,"
            f"Number of elements = {n*n:>6},"
            f"Total {total_bytes:>9} bytes"
            f"(≈ {total_bytes/1024:.1f} KB)"
        )

    # -----------------------------------------------------------------------
    #Recursion vs iteration comparison
    # -----------------------------------------------------------------------
    print("[Recursion vs Iteration] Factorial space comparison")
    n = 10
    rec = recursive_factorial(n)
    itr = iterative_factorial(n)
    print(f"Recursive factorial({n}!) = {rec}  → call stack {n} levels (O(n) space)")
    print(f"Iterative factorial({n}!) = {itr}  → only 1 variable used (O(1) space)")

    # -----------------------------------------------------------------------
    #Reference for Python integer size
    # -----------------------------------------------------------------------
    print("[Reference] Python object size")
    print(f"int (small value 28):   {sys.getsizeof(28)} bytes")
    print(f"int (large value 10^18):  {sys.getsizeof(10**18)} bytes")
    print(f"  float:              {sys.getsizeof(1.0)} bytes")
    print(f"empty list []:         {sys.getsizeof([])} bytes")
    print(f"list with 1000 elements:        {sys.getsizeof([0]*1000)} bytes (header only)")
    print("[Conclusion] Python int is much larger than C's int (4 bytes).")
    print("Be careful about memory limits when processing large data.")


if __name__ == "__main__":
    main()

# =============================================================================
#Filename: 04_complexity_compare.py
#Description: Linear search O(n) vs Binary search O(log n) comparison (measure operation count with counter)
#Time complexity: Linear search O(n), Binary search O(log n)
#Space complexity: O(1) — no additional space
# =============================================================================

import math
import time
import random


# ---------------------------------------------------------------------------
#Linear search — O(n)
#Search the array sequentially from the front
# ---------------------------------------------------------------------------
def linear_search(arr: list, target: int) -> tuple:
    """Returns the index of the target and the number of comparisons using linear search.

    Time complexity: O(n) — n comparisons in the worst case
    Space complexity: O(1)"""
    count = 0
    for i, val in enumerate(arr):  #Sequentially from the front
        count += 1
        if val == target:
            return i, count
    return -1, count  #If not found


# ---------------------------------------------------------------------------
#Binary search — O(log n)
#In a sorted array, compare with the middle value and narrow the range by half each time
# ---------------------------------------------------------------------------
def binary_search(arr: list, target: int) -> tuple:
    """Returns the index of the target and the number of comparisons using binary search.

    Preconditions: arr must be sorted in ascending order.
    Time complexity: O(log n) — the search range is halved at each step
    Space complexity: O(1)"""
    count = 0
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  #Middle index
        count += 1

        if arr[mid] == target:
            return mid, count       #Found
        elif arr[mid] < target:
            left = mid + 1          #Move to the right half
        else:
            right = mid - 1         #Move to the left half

    return -1, count  #If not found


# ---------------------------------------------------------------------------
#Visualization: Binary search step-by-step output
# ---------------------------------------------------------------------------
def binary_search_verbose(arr: list, target: int) -> int:
    """It prints the binary search process step by step."""
    left, right = 0, len(arr) - 1
    step = 0

    print(f"Search target: {target}")
    print(f"Array size: {len(arr)}")

    while left <= right:
        mid = (left + right) // 2
        step += 1
        print(
            f"Step {step}: left={left}, right={right},"
            f"mid={mid}, arr[mid]={arr[mid]}"
        )

        if arr[mid] == target:
            print(f"→ Found! Index {mid}, total {step} steps")
            return mid
        elif arr[mid] < target:
            left = mid + 1
            print(f"arr[mid] < target → move to the right")
        else:
            right = mid - 1
            print(f"arr[mid] > target → move to the left")

    print(f"→ Not found, total {step} steps")
    return -1


# ---------------------------------------------------------------------------
#Comparison benchmark
# ---------------------------------------------------------------------------
def compare_benchmark(sizes: list) -> None:
    """Compares two search algorithms on various input sizes."""
    print("\n" + "=" * 70)
    print("Linear search O(n) vs Binary search O(log n) comparison")
    print("=" * 70)
    print(
        f"{'n':>10}  {'Linear comparison count':>14}"
        f"{'Binary comparison count':>16} {'Ratio':>8}"
    )
    print("-" * 70)

    for n in sizes:
        arr = list(range(n))       #Sorted array from 0 to n-1
        target = n - 1              #Worst case: last element

        _, linear_count = linear_search(arr, target)
        _, binary_count = binary_search(arr, target)
        expected_log = int(math.log2(n)) + 1 if n > 1 else 1

        ratio = linear_count / binary_count if binary_count > 0 else 0
        print(
            f"{n:>10,}  "
            f"{linear_count:>14,} "
            f"{binary_count:>10,} (Expected log₂n≈{expected_log})"
            f"{ratio:>8.1f}x"
        )

    print("=" * 70)


def main():
    print("=" * 55)
    print("Search algorithm complexity comparison demo")
    print("=" * 55)

    # -----------------------------------------------------------------------
    #Binary search visualization (small array)
    # -----------------------------------------------------------------------
    print("[Binary search step-by-step visualization]")
    small_arr = list(range(0, 32, 2))  # [0, 2, 4, ..., 62]
    print(f"Array: {small_arr}")
    binary_search_verbose(small_arr, 42)

    # -----------------------------------------------------------------------
    #Verify search result accuracy
    # -----------------------------------------------------------------------
    print("[Result verification]")
    random.seed(42)
    test_arr = sorted(random.sample(range(1, 1001), 50))
    target = test_arr[25]  #Select middle value of the array

    lin_idx, lin_cnt = linear_search(test_arr, target)
    bin_idx, bin_cnt = binary_search(test_arr, target)

    print(f"Array size 50, target={target}")
    print(f"Linear search: Index={lin_idx}, Comparison count={lin_cnt}")
    print(f"Binary search: Index={bin_idx}, Comparison count={bin_cnt}")
    print(f"Result match: {lin_idx == bin_idx}")

    # -----------------------------------------------------------------------
    #Benchmark table
    # -----------------------------------------------------------------------
    compare_benchmark([10, 100, 1_000, 10_000, 100_000, 1_000_000])

    # -----------------------------------------------------------------------
    #Execution time comparison
    # -----------------------------------------------------------------------
    print("[Execution time comparison] n=1,000,000, Worst-case 1,000 searches")
    big_arr = list(range(1_000_000))
    target = 999_999
    repeat = 1000

    start = time.perf_counter()
    for _ in range(repeat):
        linear_search(big_arr, target)
    t_linear = time.perf_counter() - start

    start = time.perf_counter()
    for _ in range(repeat):
        binary_search(big_arr, target)
    t_binary = time.perf_counter() - start

    print(f"Linear search {repeat} times: {t_linear:.4f} seconds")
    print(f"Binary search {repeat} times: {t_binary:.6f} seconds")
    if t_binary > 0:
        print(f"Binary search is {t_linear/t_binary:.0f} times faster")


if __name__ == "__main__":
    main()