The Cost of the Three Searches

We now have three searches that answer the maze path problem: recursive backtracking, the explicit stack, and the queue.

Let the maze have $R$ rows and $C$ columns, so $R\times C$ cells. With a visited array, each cell is visited at most once. When the search visits a cell, it checks at most four adjacent positions. Four is a constant, so the total time is $O(R\times C)$.

This is true for the recursive version, the explicit stack version, and the queue version.

The space cost is also linear in the number of cells, $O(R\times C)$. The visited array uses $R\times C$ space. The recursive version may also place up to $R\times C$ calls on the call stack in a long winding maze. The stack version may store up to $R\times C$ positions in its explicit stack. The queue version may store up to $R\times C$ positions in its queue.

The Big-Oh bounds are the same for all three versions. They differ in how they behave:

• Recursive backtracking is compact because the Java call stack stores the unfinished calls.
• The explicit stack version stores that unfinished work as positions in an explicit stack, where the code can see it.
• The queue version changes the order of exploration: it visits every cell one move from the start before any cell two moves away.

The main point of this chapter is that the auxiliary data structure you pick matters. Changing it can change how the algorithm behaves, even when the rest of the code looks almost the same.