What is the A* time complexity and how is it derived?

time complexity-theory a-star
phedon rousou picture phedon rousou · May 14, 2012 · Viewed 9.6k times · Source

I was wondering if anyone could explain the A* time complexity. I am using a heuristic that uses euclidean distance for the estimate of the weight. There are no loops in the heuristic function. So i think that the time complexity of the heuristic is O(1).

Taking this into account, what would the A* complexity be and how is that derived?

Answer

yossico picture yossico · Feb 6, 2013

you can have your answer here: Why is the complexity of A* exponential in memory?

time complexity is like memory complexity

Related questions

Time complexity of unshift() vs. push() in Javascript

I know what is the difference between unshift() and push() methods in JavaScript, but I'm wondering what is the difference in time complexity? I suppose for push() method is O(1) because you're just adding an item to the end of …

Read More
Solve the recurrence: T(n)=2T(n/2)+n/logn

I can find the sum of each row (n/log n-i) and also I can draw its recursive tree but I can't calculate sum of its rows. T(n)=2T(n/2)+n/logn T(1) = 1

Read More
why does accessing an element in an array take constant time?

Lets say I have an array as: int a[]={4,5,7,10,2,3,6} when I access an element, such as a[3], what does actually happen behind the scenes? Why do many algorithm books (such as the Cormen book...) say that it takes a constant …

Read More