2
$\begingroup$

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!

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Note that $O(n\log n)\subset O(n^2)$ so your professor is making a stronger claim that does not contradict yours. $\endgroup$
    – David Richerby
    Commented Nov 3, 2014 at 8:34
  • $\begingroup$ 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. $\endgroup$
    – reinierpost
    Commented Nov 3, 2014 at 11:07
  • $\begingroup$ @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. $\endgroup$
    – Gabriel Ratener
    Commented Nov 3, 2014 at 22:02
  • $\begingroup$ No, it wouldn't. However, I haven't studied it well enough to determine whether this can actually work. $\endgroup$
    – reinierpost
    Commented Nov 3, 2014 at 23:03
  • $\begingroup$ I worked on this problem and could come up with the average case's lower bound. It was not what you stated. $\endgroup$
    – InformedA
    Commented Nov 4, 2014 at 19:15

1 Answer 1

Reset to default
2
$\begingroup$

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?

Improve this answer
$\endgroup$
5
  • $\begingroup$ The average height of the tree seems irrelevant in this case, since the algorithm must backtrack through multiple branches until it finds a series of branches that lead to a solution. $\endgroup$
    – Gabriel Ratener
    Commented Nov 4, 2014 at 18:18
  • $\begingroup$ Would the ratio of the number of cells needing to be visited to the total number of cells in the maze change as the maze scales? $\endgroup$
    – Gabriel Ratener
    Commented Nov 4, 2014 at 18:20
  • $\begingroup$ @GabrielRatener "The average height of the tree seems irrelevant in this case, since the algorithm must backtrack through multiple branches until it finds a series of branches that lead to a solution." The algorithm could have found the solution in the first branch it visits without ever having to backtrack. You need to look at average case, not worst case $\endgroup$
    – xiamx
    Commented Nov 4, 2014 at 20:04
  • $\begingroup$ True, but as n increases, the probability of never having to backtrack becomes very small. $\endgroup$
    – Gabriel Ratener
    Commented Nov 4, 2014 at 21:01
  • $\begingroup$ Try to think how many times you will backtrack in average $\endgroup$
    – xiamx
    Commented Nov 4, 2014 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.