The complete means the algorithm addresses all possible inputs, optimal means algorithm will return the best solution, optimally efficient means no other methods will cost less.
A* is complete because heuristic is always less than the real and finally it will lead to the optimal solution. The prove is same with why A* is optimal.
A* is optimal g(n)+h(n)<= real cost, g(final)+h(0)=final cost, so the algorithm will travel some possible nodes which costs less than real final cost. But the final solution must be optimal.
A* is optimally efficient: if we design h, method doesn't matter.
| Presentations on Slideshare | Lecture Notes, etc