Let's say I have an algorithm whose running time is exponential in the worst case, but I'm using a very efficient heuristic for it that in practice seems to make it work in linear time.
Basically, the algorithm has a queue, and it keeps pushing/popping items until it's empty.
For the sake of illustration, pretend the algorithm is A*, with the exception that when we reach a node twice, we don't discard the longer path -- we investigate that one as well. So, potentially, we have an exponential number of paths to investigate, but because of the heuristic, it can be linear in practice.
Clearly, the point of the question is that I can never be sure how close I am to the answer.
The only statistics I can compute efficiently for progress purposes are lower bounds on the remaining work, not upper bounds.
What is a good way to display a progress bar for such an algorithm?