In A*, we have a goal vertex. Thus, the algorithm is optimized such that in most graphs, every vertex will NOT be searched, so let’s think about how fast this algorithm runs.

Take a look at the graph.

Let’s say A is the start vertex and G is the end vertex. Through A*, we will not be searching many of the vertices left of A, so describing the runtime as the same as Dijkstra’s is not very descriptive. Remember that Dijkstra’s has a runtime of O((V+E) log V) because in the worst case you search every vertex and go through all the edges while storing data in a min-heap.

For A*, let’s try describing the runtime in better terms. Using the above graph, let’s call b the branching factor of the graph. The branching factor is the average number of edges per vertex in the graph. In this case, on average, every vertex has 2 edges, and thus, the branching factor is equal to 2. Let’s call d the depth of the goal vertex from the start vertex. Because the goal vertex is 3 edges away from the start vertex, d is equal to 3.

In the worst case, we would look at all of the edges in the direction of the goal vertex until we reach the goal vertex. We would look at b edges for every vertex in our search for close to d iterations. Thus, the runtime is O(b^d).