Theoretical worst case running time of finding a path through a maze?
If you are only interested by the worst-case scenario, you need to consider an algorithm always picking the worst possible move at any point in time. The answer is intrinsic to both the method used to find the path through the maze and the maze topology. In fact, two randomly generated mazes might be very different from each other, one could have a path from start to end with no dead end while the other might have a lot of path intersection and dead ends. In the latter, a naive algorithm might perform worse if hitting a dead end mean searching backward to the last intersection before to attempt another path. Again, the answer is intrinsic to the algorithm used to traverse the maze and the maze topology.