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!
Your question on the exam is asking for average case analysis -- visiting all the cells to solve the maze is the worst case. 

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)$?

Also try to picture this as you are exploring a tree structure. What's the average height of a tree?