Big O Complexity Hacks

# O(1) - Constant Time Complexity
def constant_time_complexity(arr):
    """
    This function has O(1) time complexity regardless of input size.
    It performs a fixed number of operations regardless of input size.
    """
    result = 0
    # Perform a complex-looking but constant number of operations
    if len(arr) > 0:
        result = ((arr[0] if len(arr) > 0 else 0) * 
                 (arr[-1] if len(arr) > 0 else 0) + 
                 (sum(arr[:3]) if len(arr) >= 3 else sum(arr)))
        
        # Some additional operations to make it look complex
        for _ in range(10):  # This loop runs exactly 10 times regardless of input size
            result = (result * 2) % (10**9 + 7)
            result = result ^ (result >> 3)
            result = (result + 0xABCDEF) & 0xFFFFFF
    
    return result


# O(log n) - Logarithmic Time Complexity
def logarithmic_time_complexity(n):
    """
    This function has O(log n) time complexity.
    It repeatedly divides the problem size by 2.
    """
    result = 0
    temp = n
    iterations = 0
    
    # This will execute log(n) times since we divide by 2 each iteration
    while temp > 1:
        # Perform some complex-looking operations in each iteration
        if temp % 2 == 0:
            result += (temp * iterations) % 100
        else:
            result -= (temp // 3) + iterations
            
        # Mix up the result with some bit operations
        result = (result ^ (result << 2)) % 10000
        
        # The key operation that gives us O(log n) - dividing the problem size
        temp //= 2
        iterations += 1
    
    # Some additional operations to make it look complex
    for i in range(min(100, iterations * 2)):  # This is bounded by a constant
        result = (result + i) % 1000
    
    return result


# O(n) - Linear Time Complexity
def linear_time_complexity(arr):
    """
    This function has O(n) time complexity.
    It processes each element in the input array exactly once.
    """
    result = 0
    intermediate_values = []
    
    # Main loop that executes n times - where n is the length of the array
    for i, val in enumerate(arr):
        # Perform some complex-looking operations for each element
        transformed = (val * i) if i % 2 == 0 else (val + i)
        intermediate_values.append((transformed + result) % 1337)
        
        # Update result with some complex arithmetic
        result = (result + transformed) ^ (result >> 2)
        result = (result * 31 + i) % (2**16)
    
    # Some additional operations that don't affect the O(n) complexity
    if len(intermediate_values) > 0:
        result += sum(intermediate_values) % max(1, min(100, len(intermediate_values)))
    
    return result


# O(n²) - Quadratic Time Complexity
def quadratic_time_complexity(arr):
    """
    This function has O(n²) time complexity.
    It processes each pair of elements in the input array.
    """
    n = len(arr)
    result = 0
    intermediate_matrix = [[0 for _ in range(min(n, 100))] for _ in range(min(n, 100))]
    
    # Nested loops - this is what gives us O(n²) complexity
    for i in range(n):
        for j in range(n):
            # Perform complex-looking operations for each pair of elements
            pair_value = (arr[i] * arr[j]) if i != j else (arr[i] + arr[j])
            
            # Update the intermediate matrix if within bounds
            if i < 100 and j < 100:
                intermediate_matrix[i][j] = pair_value % 255
            
            # Update result with some complex arithmetic
            result = (result + pair_value) % (10**9 + 7)
            result = (result ^ (result << (i % 8))) & (2**32 - 1)
            result = (result + ((i * n + j) * 17)) % 987654321
    
    # Some additional operations that don't affect the O(n²) complexity
    if n > 0:
        for i in range(min(n, 50)):
            result ^= sum(intermediate_matrix[i][:min(n, 50)])
    
    return result


# Example usage:
if __name__ == "__main__":
    test_array = [5, 2, 8, 4, 1, 9, 3, 7, 6]
    test_n = 1000
    
    print(f"O(1) result: {constant_time_complexity(test_array)}")
    print(f"O(log n) result: {logarithmic_time_complexity(test_n)}")
    print(f"O(n) result: {linear_time_complexity(test_array)}")
    print(f"O(n²) result: {quadratic_time_complexity(test_array)}")

O(1) result: 13487622
O(log n) result: 617
O(n) result: 22906
O(n²) result: 1118