# Average time to solve maze through backtracking

Given a set A consisting of all possible solvable mazes on an n by n square grid, what is the average running time to solve the mazes in A using a standard backtrack algorithm with no optimizations?

The algorithm checks each ajacent space clockwise for a channel, then visits each channel and either marks it off if it encounters a dead end, or previously covered point, or if it reaches the end point the algorithm completes.

This question was on an exam, and I figured O(n^2) cause there is O(n^2) spaces to visit for each maze, but my prof insisted the correct answer could be O(n log n).

A proof would be greatly appreciated.

Thanks!

• Note that $O(n\log n)\subset O(n^2)$ so your professor is making a stronger claim that does not contradict yours. – David Richerby Nov 3 '14 at 8:34
• You always walk a tree. What I'd try is construct larger mazes from smaller ones, e.g. by adding one row on the side, and try to count how the number of walks will increase. – reinierpost Nov 3 '14 at 11:07
• @reinierpost, but I am trying to obtain the average time for the set of all possible mazes, your method would only analyze a small subset of that set. – Gabriel Ratener Nov 3 '14 at 22:02
• No, it wouldn't. However, I haven't studied it well enough to determine whether this can actually work. – reinierpost Nov 3 '14 at 23:03
• I worked on this problem and could come up with the average case's lower bound. It was not what you stated. – InformedA Nov 4 '14 at 19:15

Informally think this way: Whenever you move to a new cell, you can move to at maximum 3 directions, which one direction is to go back to your previous cell (this choice is discarded since it's of course not what you want to do to explorer the maze.) In the two other options left, one of the direction will lead you to the target, the other one does not. What's the expectation of find the target in each move? Does it hint something $O(n \log n)$?