Course contentsShow
← Computer Science
Lesson 1009 of 2,87223. Shortest Path AlgorithmsFree lesson

A* Time and Space Complexity

Analyze how A* complexity depends on heuristic accuracy, typically exponential in worst case but practical.

A* Time and Space Complexity

You'll learn: How A*'s performance depends heavily on heuristic quality, ranging from practical efficiency to exponential blowup.

Why Complexity Is Tricky for A*

Unlike algorithms with fixed complexity like Dijkstra's O((V + E) log V), A*'s performance varies dramatically based on your heuristic function. The heuristic guides the search—a good one focuses effort efficiently, while a poor one wastes exploration.

Worst-Case Analysis

In the absolute worst case, A* can have exponential time and space complexity—O(b^d), where b is the branching factor and d is the solution depth. This happens when:

  • The heuristic provides no useful guidance (imagine h(n) = 0 everywhere—you're just doing blind search)
  • The heuristic misleads the search into exploring nearly the entire state space

Since A* keeps all explored nodes in memory for the closed set and frontier, space complexity matches time complexity in the worst case.

Practical Performance

With a good admissible and consistent heuristic, A* performs remarkably well:

  • Only explores nodes within a "focused band" toward the goal
  • Time and space become roughly O(|optimal path length| × branching factor)
  • Often exponentially faster than Dijkstra's for large search spaces

Analogy: Think of searching for treasure on an island. A terrible map (bad heuristic) forces you to dig everywhere. A perfect compass (excellent heuristic) lets you walk straight to the treasure, checking only nearby spots.

The Key Tradeoff

Better heuristics = smaller search space = better practical complexity. The accuracy of your heuristic determines whether A* is beautifully efficient or prohibitively expensive.

Key Takeaway: A* complexity is theoretically exponential but practically depends on heuristic quality—an accurate admissible heuristic keeps both time and space manageable in real-world applications.