Notes

Common Complexities

O(1) Constant Time: Execution time is the same regardless of the input size.
O(log n) Logarithmic: The execution time increases logarithmically as the input size grows.

Popcorn Hack 1:

arr = [1, 2, 3, 4, 5]

# Print the third item (index 2) — O(1) time
print("Third item:", arr[2])

# Print all items — O(n) time
print("All items:")
for item in arr:
    print(item)

Third item: 3
All items:
1
2
3
4
5

Popcorn Hack 2:

def print_unique_pairs(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            print(f"({arr[i]},{arr[j]})")

# Example usage
arr = [1, 2, 3]
print_unique_pairs(arr)

Explanation: The code has O(n²) time complexity because it uses two nested loops to generate all unique pairs. As the array size grows, the number of iterations increases proportionally to the square of the array length.

Popcorn Hack 3:

1) = Factorial time since it grows quickly

2) Quadratic time

Homework Hack 1

import time

def simulate_operations(arr, complexity):
    n = len(arr)

    print(f"Running '{complexity}' time complexity simulation with array of size {n}...")

    if complexity == "constant":
        # O(1): Accessing a single element
        print(arr[0] if arr else "Array is empty")

    elif complexity == "linear":
        # O(n): Loop through the array once
        for item in arr:
            _ = item * 2  # Example operation

    elif complexity == "logarithmic":
        # O(log n): Binary search-like behavior
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            _ = arr[mid]
            left = mid + 1  # Just advancing to simulate steps

    elif complexity == "quadratic":
        # O(n^2): Nested loop
        for i in arr:
            for j in arr:
                _ = i + j  # Example operation

    elif complexity == "cubic":
        # O(n^3): Triple nested loop
        for i in arr:
            for j in arr:
                for k in arr:
                    _ = i + j + k  # Example operation

    elif complexity == "exponential":
        # O(2^n): Fibonacci recursion (not recommended for large n)
        def fib(x):
            if x <= 1:
                return x
            return fib(x - 1) + fib(x - 2)

        if n < 20:
            _ = fib(n)  # Only safe for small n

    else:
        print("Unknown complexity type.")

    print("Operation complete.\n")