codesense/complexity.py

def estimate_complexity(features: dict) -> dict:
    """
    Estimates time complexity using heuristic rules
    based on static code features.
    """

    result = {
        "time_complexity": "O(1)",
        "explanation": "No loops or recursion were detected, suggesting constant time operations."
    }

    max_depth = features.get("max_loop_depth", 0)

    # ----- BFS/DFS Pattern -----
    if features.get("bfs_pattern") or features.get("dfs_pattern"):
        return {
            "time_complexity": "O(V + E)",
        }

    # ----- Binary search heuristic -----
    if features.get("binary_search_pattern"):
        result["time_complexity"] = "O(log n)"
        return result
    
    # ----- Dynamic Programming -----
    if features.get("dp_pattern"):
        result["time_complexity"] = "O(n) or O(n²)"
        # result["explanation"] = (
        #     "Dynamic programming detected. Complexity depends on the number "
        #     "of states and transitions."
        # )
        return result

    # ----- Merge Sort -----
    if features.get("merge_sort_pattern"):
        return {
            "time_complexity": "O(n log n)"
        }

    # ----- Quick Sort -----
    if features.get("quick_sort_pattern"):
        return {
            "time_complexity": "O(n log n) average, O(n²) worst-case"
        }

    # ----- Recursion Heuristics -----
    if features["recursion"]:

        if features.get("divide_and_conquer"):
            result["time_complexity"] = "O(n log n)"
            return result

        if features["recursive_call_count"] >= 2:
            result["time_complexity"] = "O(2^n)"
            return result

        result["time_complexity"] = "O(n)"
        return result
    
    # ----- Sorting Algorithms -----
    if features.get("bubble_sort_pattern"):
        return {
            "time_complexity": "O(n²) worst-case (O(n) best-case if optimized)"
        }

    if features.get("insertion_sort_pattern"):
        return {
            "time_complexity": "O(n²) worst-case (O(n) best-case for nearly sorted input)"
        }   

    # ----- Sliding Window -----
    if features.get("sliding_window_pattern"):
        return {
            "time_complexity": "O(n)"
        } 
    
    # ----- Heap-Based -----
    if features.get("heap_pattern"):
        return {
            "time_complexity": "O(n log n) or O(log n) per operation"
        }

    # ----- Iterative Heuristics -----
    if max_depth == 1:
        result["time_complexity"] = "O(n)"
        return result

    if max_depth >= 2:
        result["time_complexity"] = f"O(n^{max_depth})"
        return result


    return result