Given a non-admissible heuristic function, A* will always give a solution if one exists, but there is no guarantee it will be optimal.
I won't duplicate the proof here, but it isn't too hard to prove that any best-first search will find a solution for any measure of best, given that a path to the solution exists and infinite memory. A* is a best-first ...
No misunderstanding. IDA* is indeed n^2 vs n for A* in certain situations.
for a reference.
IDA* only works in certain (not uncommon) situations. If there are many states with the same costs, and this number grows exponentially with the cost, then IDA* will be O(n). An example ...