Greedy Best-First Search vs. UCS: Fast but Wrong vs. Slow but Optimal

Q: Saying Greedy is optimal if the heuristic is admissible

Admissibility does NOT make Greedy optimal. Admissibility ($h(n) \leq h^*(n)$) is the condition that makes A* optimal — because A* also tracks $g(n)$. Greedy ignores $g(n)$ entirely, so even with a perfect admissible heuristic, it can take a route that looks close to the goal but has an astronomically high actual cost.

Q: Saying UCS is complete even with zero-cost edges

UCS completeness requires strictly positive edge costs ($\epsilon > 0$). If some edges cost $0$, $g(n)$ never increases along those edges and UCS can loop forever expanding zero-cost nodes without making progress toward the goal.

Try Greedy Solver →Try Uniform Solver →

TL;DR — Greedy Best-First Search and UCS are mirror opposites. Greedy expands nodes based purely on $h(n)$ — the estimated cost from node $n$ to the goal — completely ignoring how much it already cost to get there. It's like navigating by 'which direction feels closer to my destination' without tracking the distance you've already walked. UCS does the exact opposite: it expands nodes based purely on $g(n)$ — the actual cost from the start to node $n$ — completely ignoring how far the goal might be. Greedy is fast but reckless; it can happily walk down a cheap-looking path that dead-ends expensively. UCS is methodical and guaranteed to find the cheapest path, but it wastes effort exploring nodes in all directions with no sense of where the goal actually is. A* fixes both by combining them: $f(n) = g(n) + h(n)$ .

Feature Comparison

Feature	Greedy Best-First Search	Uniform Cost Search (UCS)
Priority Function	$f(n) = h(n)$ — expand whichever node looks closest to the goal according to the heuristic	$f(n) = g(n)$ — expand whichever node has the lowest actual cost from the start
Uses a Heuristic	Yes — entirely depends on $h(n)$ ; this is the only information it uses to make decisions	No — purely cost-driven; has zero knowledge of the goal's location or estimated remaining distance
Tracks Path Cost So Far	No — $g(n)$ is completely ignored; it doesn't matter how expensive the path to $n$ was	Yes — $g(n)$ is the entire priority function; every expansion is based on total accumulated cost
Optimality	Not guaranteed — Greedy can and often does return a suboptimal solution, even with a perfect heuristic	Guaranteed — always finds the lowest-cost path, provided edge costs are positive
Completeness	Not complete in general — can get trapped in infinite loops if revisited states are not tracked	Complete — will always find a solution if one exists, as long as edge costs are $> 0$
Speed (Typical Case)	Faster in practice — a good $h(n)$ sends it almost straight to the goal, expanding very few nodes	Slower — expands every node whose $g(n)$ is less than the optimal solution cost, spreading in all directions
Search Behavior	Tunnel-visioned — greedily follows the heuristic's suggestion at every step; can overshoot or loop	Flood-fill style — radiates outward from the start in order of cumulative cost, ignoring goal direction
Sensitivity to Heuristic Quality	Extremely sensitive — a poor $h(n)$ causes terrible performance or completely wrong answers	Immune — no heuristic is used; performance is consistent regardless of problem domain knowledge
Relation to A*	A* with $g(n)$ removed — it's the 'optimistic half' of A* without the cost-tracking safety net	A* with $h(n) = 0$ — it's the 'cautious half' of A* without any directional guidance
Typical Use Case	Problems where a fast approximate answer is acceptable and a good heuristic is available — e.g., rough navigation, puzzle pre-processing	Problems with no natural heuristic, or wherever finding the provably cheapest path is required

Complexity Showdown

Training Time

Greedy:N/A — search algorithms have no training phase

Uniform:N/A — search algorithms have no training phase

Neither algorithm trains. Complexity is measured in nodes expanded and memory used at search time.

Prediction Time

Greedy:

O(b^m)

worst case where

b

is branching factor and

m

is max depth — but in practice much less with a good heuristic

Uniform:

O(b^{1 + \lfloor C^*/\epsilon \rfloor})

where

C^*

is optimal solution cost and

\epsilon

is the minimum edge cost

Greedy typically expands far fewer nodes than UCS because it ignores irrelevant low-cost nodes and drives straight toward the goal. However, this advantage disappears when the heuristic is misleading — Greedy can expand more nodes than UCS in adversarial cases. UCS is predictable; Greedy's performance is heuristic-dependent.

Space Complexity

Greedy:

O(b^m)

— must store all generated nodes in the worst case

Uniform:

O(b^{1 + \lfloor C^*/\epsilon \rfloor})

— stores all nodes with cost

\leq C^*

Both algorithms store their frontier and explored sets in memory. In practice Greedy uses less memory because it generates fewer nodes, but worst-case complexity class is the same for both.

When To Use Which?

Use Greedy Best-First Search when:

✓Speed matters more than correctness — if you need a quick, good-enough path and a suboptimal answer is acceptable, Greedy will typically get there faster than UCS.
✓You have a reliable, informative heuristic — the closer $h(n)$ is to the true remaining cost, the better Greedy performs. On a grid map, straight-line distance is nearly perfect.
✓The problem space is huge and exhaustive search is impractical — Greedy's aggressive pruning makes it usable in scenarios where UCS would run out of memory or time.
✓You're building a heuristic-first prototype — Greedy is easy to implement and can reveal how good your heuristic is before you invest in a full A* implementation.
✓Approximate solutions are fine — games, real-time simulations, or decision systems where 'good enough fast' beats 'perfect but slow'.

Use UCS when:

✓Optimality is required and no reliable heuristic exists — UCS is your safest optimal algorithm when you can't estimate remaining cost without risking overestimation.
✓Edge costs vary significantly — if some paths are much more expensive than others, BFS will give wrong answers and UCS is the correct uninformed choice.
✓You need shortest paths to all reachable nodes — UCS naturally computes optimal costs to every node it explores, not just the single goal.
✓Simplicity and reliability are priorities — UCS has no hyperparameters, no domain knowledge requirements, and no failure modes caused by a bad heuristic.
✓Correctness guarantees are non-negotiable — safety-critical systems, formal verification, or exam problems asking for the provably optimal solution.

Common Exam Traps

⚠️

Saying Greedy is optimal if the heuristic is admissible

Admissibility does NOT make Greedy optimal. Admissibility ( $h(n) \leq h^*(n)$ ) is the condition that makes A* optimal — because A* also tracks $g(n)$ . Greedy ignores $g(n)$ entirely, so even with a perfect admissible heuristic, it can take a route that looks close to the goal but has an astronomically high actual cost.

⚠️

Confusing Greedy Best-First with Greedy algorithms in general

In search, 'Greedy' specifically refers to Greedy Best-First Search using $f(n) = h(n)$ . General greedy algorithms (like Greedy for coin change or Kruskal's MST) are a different paradigm. Don't mix these up on an exam — they share a philosophy but are different algorithms in different contexts.

⚠️

Saying UCS is complete even with zero-cost edges

UCS completeness requires strictly positive edge costs ( $\epsilon > 0$ ). If some edges cost $0$ , $g(n)$ never increases along those edges and UCS can loop forever expanding zero-cost nodes without making progress toward the goal.

⚠️

Thinking Greedy is always faster than UCS

Greedy is typically faster in practice with a good heuristic, but it's not guaranteed. A misleading heuristic can send Greedy down a long wrong path, causing it to expand more nodes than UCS. In the worst case with a terrible heuristic, Greedy can be slower and still return the wrong answer.

⚠️

Claiming Greedy is incomplete because it uses a heuristic

Greedy's incompleteness is caused by the lack of cycle detection and the absence of $g(n)$ tracking — not by the heuristic itself. If you add a visited-states check, Greedy becomes complete in finite state spaces. The heuristic is not the culprit for incompleteness.

Final Verdict

Greedy Best-First Search and UCS each take one half of what makes A* powerful. Greedy takes the heuristic ( $h(n)$ ) and throws away cost-tracking — fast, directional, but reckless and non-optimal. UCS takes the cost-tracking ( $g(n)$ ) and throws away the heuristic — slow, exhaustive, but always correct. If you only have one of the two ingredients, your algorithm sacrifices either speed or correctness. A* is the answer when you have both. Choose Greedy when you need speed and can tolerate suboptimal results. Choose UCS when you need the provably cheapest path and have no reliable heuristic.

Greedy Best-First Search

Try the Greedy Solver →Read Greedy Theory Guide

Uniform Cost Search (UCS)

Try the Uniform Solver →Read Uniform Theory Guide