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 O(n log n), 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.

def min_rooms_sweep(meetings):
    starts = sorted(s for s, _ in meetings)
    ends = sorted(e for _, e in meetings)
    rooms = j = 0
    for s in starts:
        if ends[j] <= s:
            j += 1      # inherit the room of a meeting that has ended
        else:
            rooms += 1  # open another room
    return rooms


print(min_rooms_sweep([(9, 10), (9, 12), (10, 11), (11, 13), (12, 13)]))  # 2

Compared with alternatives

Where greedy is correct it beats the alternatives on both time and memory. But small changes to the problem (adding weights, making items indivisible) take the guarantee away. When the problem changes, re-check correctness before you worry about complexity.

Measure it yourself

You can check the theory against wall-clock time. If time grows a bit more than tenfold when n grows tenfold, that matches O(n log n).

import random
import time


def max_count(intervals):
    count, last_end = 0, float("-inf")
    for start, end in sorted(intervals, key=lambda iv: iv[1]):
        if start >= last_end:
            count, last_end = count + 1, end
    return count


for n in (10_000, 100_000, 1_000_000):
    data = [(s, s + random.randint(1, 100)) for s in (random.randint(0, 10**6) for _ in range(n))]
    t = time.perf_counter()
    max_count(data)
    print(n, f"{time.perf_counter() - t:.3f}s")

Summary

• Greedy running time is dominated by sorting or heap operations and is usually O(n log n).
• With pre-sorted input, both activity selection and Huffman coding drop to O(n).
• Use the two-pointer sweep when you only need a room count, the heap when you need the assignment.
• Greedy is the fastest option when it is correct, but weights or indivisible items call for dynamic programming.