# A\* time complexity
**URL:** https://discussions.unity.com/t/a-time-complexity/423785
**Category:** Navigation
**Tags:** Scripting
**Created:** [September 24, 2010, 7:09am UTC](https://discussions.unity.com/t/a-time-complexity/423785 "2010-09-24T07:09:04Z")
**Posts on this page:** 9
**Page:** 1
### Author:  [@anon\_27012712](https://discussions.unity.com/u/anon_27012712)
#### Post date: [September 24, 2010, 7:09am UTC](https://discussions.unity.com/t/a-time-complexity/423785/1 "2010-09-24T07:09:04Z")
Hello !!!
I am a bit confused with A\* time complexity. I can not understand why the complexity depends on the Heuristic function , according to the wikipedia
> **[A\* search algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm)**
>
> A\* (pronounced "A-star") is a graph traversal and pathfinding algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. Given a weighted graph, a source node and a goal node, the algorithm finds the shortest path (with respect to the given weights) from source to goal.
> One major practical drawback is its
>
>
>
> O
> (
>
> b
>
> d
>
>
> )
>
>
> {\\d...
What’s the time complexity damn it :twisted: :twisted: :twisted: :twisted: :twisted:
---
### Author:  [@anon\_30685870](https://discussions.unity.com/u/anon_30685870)
#### Post date: [September 24, 2010, 8:34am UTC](https://discussions.unity.com/t/a-time-complexity/423785/2 "2010-09-24T08:34:51Z")
I’m working on A\* too and i’ve understand the more your Heuristic evaluation is good, the more your pathfinding will be fast, but i don’t remember exactly why.
[http://www.policyalmanac.org/games/aStarTutorial.htm](http://www.policyalmanac.org/games/aStarTutorial.htm) may explain it better than me
---
### Author:  [@anon\_43237147](https://discussions.unity.com/u/anon_43237147)
#### Post date: [September 24, 2010, 9:13am UTC](https://discussions.unity.com/t/a-time-complexity/423785/3 "2010-09-24T09:13:43Z")
Time complexity is an analytical assessment of how the amount of time an algorithm takes to execute is related to the number of inputs or data points the algorithm runs over. In the case of A\*, the heuristic function is invoked for each pair of nodes in the search graph, so the higher its execution cost, the higher the execution cost of the entire A\* algorithm.
Put in much simpler terms: the more expensive/inefficient your heuristic function is, the slower your A\* searches will run.
---
### Author:  [@anon\_27012712](https://discussions.unity.com/u/anon_27012712)
#### Post date: [September 24, 2010, 12:06pm UTC](https://discussions.unity.com/t/a-time-complexity/423785/4 "2010-09-24T12:06:38Z")
Well, i just use the Euclidian distance for Heurestic :? :? :? :? :?
---
### Author:  [@andeeeee](https://discussions.unity.com/u/andeeeee)
#### Post date: [September 24, 2010, 3:47pm UTC](https://discussions.unity.com/t/a-time-complexity/423785/5 "2010-09-24T15:47:49Z")
A\* has other uses beyond pathfinding, so the heuristic can be very abstract in some cases. For pathfinding, the Euclidean distance is a good choice when searching through waypoints at arbitrary positions in space. However, if the game is played on a grid where only horizontal and vertical moves are allowed, then the rectilinear or “Manhattan” distance is a better estimate. There may be other factors you can take into account, too. Say, for example, that all paths to a target go through a single waypoint, a narrow bridge between two riverbanks, perhaps. You could just use the Euclidean distance from start to target, but in reality, the path will have to go across the bridge. You can therefore get a more accurate estimate in this case by getting the distance to the bridge and then from the bridge to the target and adding them together. This will speed up the search because the algorithm is less likely to try positions along the riverbank that are near to the target in Euclidean terms, but are nowhere near the bridge.
---
### Author:  [@anon\_27012712](https://discussions.unity.com/u/anon_27012712)
#### Post date: [September 24, 2010, 5:40pm UTC](https://discussions.unity.com/t/a-time-complexity/423785/6 "2010-09-24T17:40:18Z")
Andeeee your thoughts on Manhattan-Euclidian distance are correct but what i’m trying to find out is different.
Let’s take A\* step by step:
At first we search the openList(simple Linked List) for the least cost node we have a complexity of O(n)
Then we searh the closed list to see if that node is already searched.Complexity O(n)
Finally we add a new node to the open list O(1)
So the overall complexity is O(n).
The Heurestic has no complexity at all, it is just multiplication.
Maybe there is a connection between the Heurestic method and how many loops are done in order to get our result.
I think it is very weird that there is no explanation for the | h(x) − h \* (x) | = O(logh \* (x)) :? :? :? :?
---
### Author:  [@anon\_63648089](https://discussions.unity.com/u/anon_63648089)
#### Post date: [September 24, 2010, 5:43pm UTC](https://discussions.unity.com/t/a-time-complexity/423785/7 "2010-09-24T17:43:06Z")
> [@""](#):
>
> Andeeee your thoughts on Manhattan-Euclidian distance are correct but what i’m trying to find out is different.
> Let’s take A\* step by step:
>
> At first we search the openList(simple Linked List) for the least cost node we have a complexity of O(n)
> Then we searh the closed list to see if that node is already searched.Complexity O(n)
> Finally we add a new node to the open list O(1)
>
> So the overall complexity is O(n).
>
> The Heurestic has no complexity at all, it is just multiplication.
>
> Maybe there is a connection between the Heurestic method and how many loops are done in order to get our result.
>
> I think it is very weird that there is no explanation for the | h(x) − h \* (x) | = O(logh \* (x)) :? :? :? :?
If your heuristic is an oracle for distance that doesn’t need to check every element at a particular depth, you can do better than O(n). Look at the part of the page where it talks about optimal heuristic. If your heuristic is perfectly optimal, then your complexity is Theta( log(n) ).
---
### Author:  [@anon\_43237147](https://discussions.unity.com/u/anon_43237147)
#### Post date: [September 24, 2010, 8:29pm UTC](https://discussions.unity.com/t/a-time-complexity/423785/8 "2010-09-24T20:29:42Z")
Also note that an assumption of O(n) complexity for searching the open list is only valid if the heuristic cost can be determined directly from the node; in more abstract search graphs, it’s possible more nodes would need to be considered to generate a reasonable heuristic – especially if the graph has a higher order dimensionality, which isn’t hard once you get away from (2- or 3-dimensional) spatial graphs.
ETA: also, look at Theta\*, a path optimizing variant of A\*, which needs to do line-of-sight tests and euclidean distance calculations for path relaxation at each expansion…
---
### Author:  [@anon\_27012712](https://discussions.unity.com/u/anon_27012712)
#### Post date: [September 25, 2010, 4:56pm UTC](https://discussions.unity.com/t/a-time-complexity/423785/9 "2010-09-25T16:56:09Z")
Ok, I’m starting to get the picture 😄 , and i’ve found a very usefull link which explains a lot :
[http://www.ai.mit.edu/courses/6.034b/searchcomplex.pdf](http://www.ai.mit.edu/courses/6.034b/searchcomplex.pdf)
So my conclusion is that the worst case for A\* is O(b^(d+1)) but practically is less than that because of the heurestic. In order to make the A\* run in polyonimal time we have to satisfy | h(x) − h \* (x) | = O(logh \* (x)) but we cannot calculate h\*(x) , cause if we could we would use it !.
Finally a quote from the book: Artificial intelligence, a modern approach
> [@](#):
>
> For almost all heuristics in practical use, the error is at least proportional to the path cost, and the resulting exponential growth eventually ovretakes any computer.
To make the long story short O(b^(d+1)) :shock: :shock: :shock: :shock: