14.21 Complexity Analysis

Greedy algorithms often have simple control flow. Sort the input, scan once, push into a heap, pop from a heap, or union two components. Because the code is usually compact, it is tempting to assume the complexity is obvious.

That assumption is risky.

The cost of a greedy algorithm is usually hidden in the supporting operation:

Sort
Heap push
Heap pop
Find
Union
Tree lookup
Stack update

This recipe shows how to analyze greedy algorithms by identifying the dominant operation and counting how often it occurs.

Problem

Given a greedy algorithm, determine its time and space complexity accurately.

The main questions are:

Does the algorithm sort?
Does it scan once or many times?
Does it use a heap?
Does it use union-find?
Does it maintain an ordered structure?
Does each item enter and leave the structure once?
Does the implementation accidentally rescan data?

The Basic Pattern

Most greedy algorithms have this shape:

Preprocess input

Initialize state

For each item:
    inspect item
    update state
    maybe insert into structure
    maybe remove from structure

Return answer

The complexity is the sum of these pieces.

A typical greedy algorithm is not expensive because it makes difficult decisions. It is expensive because it must maintain the data needed to make those decisions efficiently.

Sorting-Dominated Greedy Algorithms

Many greedy algorithms start by sorting.

Examples:

Algorithm	Sort Key	Scan
Interval scheduling	Finish time	Select compatible intervals
Fractional knapsack	Density	Take capacity
Activity selection	Finish time	Select activities
Merge intervals	Start time	Extend ranges
Rescue boats	Weight	Move two pointers

Sorting costs:

O(n log n)

The scan usually costs:

O(n)

Total:

O(n log n)

Space depends on the sorting implementation and output storage.

Example: Interval Scheduling

Algorithm:

Sort intervals by finish time.
Scan once.
Accept interval if compatible.

Cost:

Step	Cost
Sort intervals	`O(n log n)`
Scan intervals	`O(n)`
Store result	`O(k)`

Total time:

O(n log n)

Space:

O(k)

for the result, where k is the number of selected intervals.

If the result is only counted, auxiliary space is:

O(1)

excluding sort internals.

Heap-Dominated Greedy Algorithms

Priority queues appear when candidates become available dynamically.

Examples:

Algorithm	Heap Type	Operation
Huffman coding	Min-heap	Extract two smallest
Minimum refueling stops	Max-heap	Extract largest fuel
Course scheduling	Max-heap	Remove longest job
Meeting rooms	Min-heap	Reuse earliest room
Dijkstra	Min-heap	Extract closest vertex
Prim	Min-heap	Extract cheapest edge

Each heap operation costs:

O(log n)

If each item is pushed and popped at most once, the total heap cost is:

O(n log n)

Example: Minimum Refueling Stops

Each station is inserted into the heap once.

Each selected station is popped at most once.

Step	Count	Cost
Push station	`n`	`O(log n)`
Pop station	at most `n`	`O(log n)`

Total:

O(n log n)

Space:

O(n)

for the heap.

The key observation is not the loop count alone. The loop may contain nested while statements, but every station advances through the algorithm once.

Nested Loops Can Still Be Linear

Many greedy algorithms contain nested loops but remain linear after sorting.

Example:

for reach < target:
    while next station is reachable:
        push station
    pop best station

This looks nested.

But the inner loop advances a station index that never moves backward.

Each station is processed once.

Therefore the total number of inner-loop iterations over the whole algorithm is n, not n per outer iteration.

This is amortized reasoning.

Union-Find Greedy Algorithms

Kruskal's algorithm is the standard example.

Steps:

Sort edges by weight.
For each edge, check whether its endpoints are already connected.
Union components when the edge is accepted.

Sorting:

O(E log E)

Union-find operations:

O(E α(V))

where α is the inverse Ackermann function, effectively constant for practical input sizes.

Total:

O(E log E)

because sorting dominates.

Ordered-Set Greedy Algorithms

Some greedy algorithms require operations such as:

Find smallest value >= x
Find largest value <= x
Delete value
Insert value

These are not heap operations.

They require a balanced search tree or equivalent ordered structure.

Each operation typically costs:

O(log n)

If performed once per item:

O(n log n)

Examples include resource assignment, interval allocation, and matching problems with ordered capacities.

Stack-Based Greedy Algorithms

Monotonic stack algorithms often run in linear time.

Examples:

Remove duplicate letters.
Remove k digits.
Next greater element.
Largest rectangle in histogram.

The key fact is:

Each element is pushed once and popped at most once.

Therefore total stack operations are:

O(n)

Even if the code contains a while loop inside a for loop, total popping is bounded by the number of pushes.

Example: Remove k Digits

For each digit:
    while stack top is larger and k > 0:
        pop
    push digit

Each digit is pushed once.

Each digit can be popped once.

Total time:

O(n)

Space:

O(n)

for the stack.

Two-Pointer Greedy Algorithms

Two-pointer greedy algorithms are also typically linear after sorting.

Example:

left = 0
right = n - 1

while left <= right:
    decide
    move left, right, or both

Each pointer moves in only one direction.

Total pointer movements:

O(n)

If sorting is required:

O(n log n)

If input is already sorted:

O(n)

Example: Rescue Boats

Sorting weights:

O(n log n)

Pointer scan:

O(n)

Total:

O(n log n)

Space:

O(1)

excluding sort internals.

Complexity Table

Pattern	Typical Time	Typical Space
Sort + scan	`O(n log n)`	`O(1)` to `O(n)`
Sort + two pointers	`O(n log n)`	`O(1)`
Heap greedy	`O(n log n)`	`O(n)`
Union-find after sorting	`O(E log E)`	`O(V)`
Monotonic stack	`O(n)`	`O(n)`
Ordered tree	`O(n log n)`	`O(n)`
Frequency array	`O(n + σ)`	`O(σ)`

Here σ is the alphabet or key-space size.

Space Complexity

Space analysis should distinguish between:

Input storage
Output storage
Auxiliary storage
Sorting workspace
Data structure storage

For example, interval scheduling may store selected intervals.

If the output contains k intervals, output space is:

O(k)

Auxiliary space may still be:

O(1)

Similarly, Huffman coding stores tree nodes.

For n symbols, the final tree contains:

2n - 1

nodes.

Thus space is:

O(n)

Beware of Hidden Copies

In languages such as Go, implementation details matter.

This code may copy data:

result = append(result, current)

That is fine for small structs.

But if the item is large, storing pointers may be better.

Similarly, sorting in place mutates input:

sort.Slice(items, ...)

If the caller expects the original order preserved, copy first:

items = append([]Item(nil), items...)

That copy costs:

O(n)

space and time.

Numeric Costs

Greedy algorithms often compare values such as:

value / weight

Be careful with floating-point density.

Instead of comparing:

a.Value/a.Weight > b.Value/b.Weight

prefer cross multiplication when values are integers:

a.Value*b.Weight > b.Value*a.Weight

This avoids precision errors.

However, cross multiplication can overflow for large values.

In that case, use wider integer types or arbitrary precision arithmetic.

Complexity analysis should include numeric model assumptions when values may be large.

When Greedy Is Linear

A greedy algorithm can be linear when:

Input is already ordered.
The key space is bounded.
A stack or queue suffices.
Frequency arrays replace maps or heaps.
Each element is processed a constant number of times.

Examples:

Problem	Reason
Remove k digits	Each digit pushed and popped once
Partition labels	Fixed alphabet last-occurrence array
Subsequence matching	Single scan
Already sorted interval scan	No sorting needed
Counting-based greedy	Bounded key space

The absence of sorting or logarithmic operations usually indicates possible linear time.

When Greedy Becomes Quadratic

Greedy implementations often become quadratic by accident.

Common causes:

Repeated Scanning

For each decision:
    scan all candidates

Rebuilding Heaps

For each step:
    build priority queue again

Removing from the Front of Arrays

In Go, repeatedly doing:

a = a[1:]

may keep references to the underlying array longer than intended.

In some languages, front removal itself is linear.

Checking Feasibility Expensively

For graph algorithms, checking whether an edge creates a cycle by running DFS each time is much slower than union-find.

Amortized Analysis

Many efficient greedy algorithms rely on amortized bounds.

The argument is:

Even though one iteration may do many operations,
each element participates in those operations only a bounded number of times.

Examples:

Algorithm	Amortized Reason
Monotonic stack	Each element popped once
Refueling stops	Each station pushed once
Sliding heap patterns	Each event inserted once
Two pointers	Each pointer moves one direction
Union-find	Path compression reduces future cost

Amortized analysis is often the cleanest way to explain greedy performance.

Proof and Complexity Are Separate

Correctness and complexity answer different questions.

Correctness asks:

Does this greedy rule produce an optimal solution?

Complexity asks:

How much work does the implementation perform?

A greedy algorithm may be correct but slow.

A greedy algorithm may be fast but incorrect.

Both analyses are required.

Takeaway

Complexity analysis for greedy algorithms usually reduces to identifying the dominant supporting operation. Sorting gives O(n log n), heaps give logarithmic insertion and removal, union-find makes connectivity checks effectively constant, stacks and two pointers often give linear scans, and ordered trees support successor queries in logarithmic time. Nested loops do not automatically imply quadratic behavior; count how many times each item enters, leaves, or moves through the data structure. A precise greedy analysis separates the proof of optimality from the cost of maintaining the state needed to make each greedy choice.