Complexity

The cost of a greedy algorithm usually comes from sorting or priority-queue operations; the choice itself is often constant time per candidate. That is why the classic greedy algorithms typically run in O(n log n), dropping to O(n) when the input is already sorted.

Complexity by problem

Best, average and worst cases barely differ. Sorting costs O(n log n) regardless of input shape (Python's Timsort drops to O(n) on already sorted data), and the scan that follows is always a single pass. In the meeting-room algorithm the heap never holds more than k entries, the maximum number of simultaneous meetings, so the tighter bound is O(n log k).

Linear-time Huffman with two queues

When frequencies are already sorted ascending, you can compute the Huffman cost with two queues and no heap. Merged weights come out in non-decreasing order, so the second queue stays sorted by itself.

from collections import deque


def huffman_cost_sorted(weights):
    """Total encoded bits for ascending weights, in O(n)."""
    leaves, merged = deque(weights), deque()

    def pop_min():
        if not merged or (leaves and leaves[0] <= merged[0]):
            return leaves.popleft()
        return merged.popleft()

    total = 0
    while len(leaves) + len(merged) > 1:
        a = pop_min()
        b = pop_min()
        total += a + b
        merged.append(a + b)
    return total


print(huffman_cost_sorted([5, 9, 12, 13, 16, 45]))  # 224

Counting rooms without a heap

If you only need the number of rooms, sort start and end times separately and sweep with two pointers. It is still , but with smaller constants and less code. It does not tell you which meeting goes in which room, so use the heap version when you need the assignment.