If h(n) is a perfect heuristic (that is, h(n) = h*(n)), then does it imply that A* will always take linear time complexity?
First, to be specific I’m going to assume your heuristic function runs in constant time and we have a graph G with n nodes, and that you are asking about linearity with respect to n.

I claim that in the worst case A* will run in quadratic time.

Suppose G is a complete graph where every edge has a weight of 10000 except for the “true path” which winds from the starting node along every other node until the final node, and these edges have weight 1.

By definition of A*, every time we visit a node, we look across all its edges to queue up nodes into our priority queue of paths to explore. By construction, we visit every node and hence consider every edge. It is a complete graph on n nodes, so there is roughly n^2 edges, thus this process takes quadratic time