Prove the relation between space complexity and time complexity of the graph search which uses "the explored set"

I was referring to the textbook Artificial Intelligence: A modern approach 3rd by Stuart Russell and Peter Norvig.

what to prove about the general "graph search": (Here I assume "within a factor of b" means multiplier $$b$$ instead of addition $$\pm b$$ based on the complexity context. So if time complexity is $$O(b^d)$$, then space complexity is $$O(b^d)\sim O(b^d\cdot b)$$ although here $$b$$ is constant. Here I use $$\sim$$ to indicate the range instead of the asymptotical relation)

As for space complexity: for any kind of graph search, which stores every expanded node in the explored set, the space complexity is always within a factor of b of the time complexity

$$b$$ is defined in 3.4.1 Breadth-first search:

For these reasons, complexity is expressed in terms of three quantities: b, the branching factor or maximum number of successors of any node; d, the depth of the shallowest goal node (i.e., the number of steps along the path from the root); and m, the maximum length of any path in the state space.

1. pseudocodes for the general "graph search" offered by the textbook

As the saying goes, algorithms that forget their history are doomed to repeat it. The way to avoid exploring redundant paths is to remember where one has been. To do this, we augment the TREE-SEARCH algorithm with a data structure called the explored set (also known as the closed list), which remembers every expanded node. Newly generated nodes that match previously generated nodes—ones in the explored set or the frontier—can be discarded instead of being added to the frontier. The new algorithm, called GRAPH-SEARCH, is shown informally in Figure 3.7. The specific algorithms in this chapter draw on this general design.

Here I show the text version to help the search while keeping the image due to the format like bold, italics will help understanding the problem.

function TREE-SEARCH(problem) returns a solution, or failure
initialize the frontier using the initial state of problem
loop do
if the frontier is empty then return failure
choose a leaf node and remove it from the frontier
if the node contains a goal state then return the corresponding solution
expand the chosen node, adding the resulting nodes to the frontier
function GRAPH-SEARCH(problem) returns a solution, or failure
initialize the frontier using the initial state of problem
initialize the explored set to be empty
loop do
if the frontier is empty then return failure
choose a leaf node and remove it from the frontier
if the node contains a goal state then return the corresponding solution
add the node to the explored set
expand the chosen node, adding the resulting nodes to the frontier
only if not in the frontier or explored set
Figure 3.7 An informal description of the general tree-search and graph-search algorithms. The parts of GRAPH-SEARCH marked in bold italic are the additions needed to
handle repeated states.

The space complexity is caused by the frontier and the explored set.

• The book doesn't pay much attention to the general "graph search"

For the most part, we describe time and space complexity for search on a tree; for a graph, the answer depends on how “redundant” the paths in the state space are.

2. For BFS tree, the textbook says about its time complexity:

Now suppose that the solution is at depth d. In the worst case, it is the last node generated at that level. Then the total number of nodes generated is $$b + b^2 + b^3 + \cdots + b^d = O(b^d)$$

For breadth-first graph search in particular, every node generated remains in memory. There will be $$O(b^{d−1})$$ nodes in the explored set and $$O(b^{d})$$ nodes in the frontier, so the space complexity is $$O(b^{d})$$, i.e., it is dominated by the size of the frontier. Switching to a tree search would not save much space, and in a state space with many redundant paths, switching could cost a great deal of time

pseudocodes offered by the textbook (The above "$$O(b^{d})$$ nodes in the frontier" is ensured by tree which won't repeatedly access one same vertex)

function BREADTH-FIRST-SEARCH(problem) returns a solution, or failure
node <-a node with STATE = problem.INITIAL-STATE, PATH-COST = 0
if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
frontier <- a FIFO queue with node as the only element
explored <- an empty set
loop do
if EMPTY?(frontier ) then return failure
node <- POP(frontier ) /* chooses the shallowest node in frontier */
for each action in problem.ACTIONS(node.STATE) do
child <- CHILD-NODE(problem, node, action)
if child.STATE is not in explored or frontier then
if problem.GOAL-TEST(child.STATE) then return SOLUTION(child)
frontier <- INSERT(child,frontier )
Figure 3.11 Breadth-first search on a graph

• relation between BFS and the general graph search

Breadth-first search is an instance of the general graph-search algorithm (Figure 3.7) in which the shallowest unexpanded node is chosen for expansion. This is achieved very simply by using a FIFO queue for the frontier.

I can understand the calculation of BFS tree complexity. But I have the confusion about its interior "general graph-search algorithm".

• Here both complexities are based on "the total number of nodes" for tree with the same $$O(b^d)$$. Then for the general graph, it should have one radial structure similar to the tree but having less children to avoid repeatedly visiting one same vertex (this is where redundant paths occur).

If you are concerned about reaching the goal, there’s never any reason to keep more than one path to any given state, because any goal state that is reachable by extending one path is also reachable by extending the other.

Redundant paths doesn't increase the number of nodes, but it may decrease the number of nodes (i.e. frontier nodes may be all have been visited before, so no $$O(b^d)$$. Then space complexity becomes $$O(b^{d-1})$$ which is less than time complexity $$O(b^d)$$) compared with tree which won't repeatedly visiting one same vertex. So its space complexity should be less than time complexity instead of "within a factor of b".

Then it seems that "within a factor of b" may mean that if time complexity is $$O(b^d)$$, then space complexity is $$O(b^d\cdot \frac{1}{b})\sim O(b^d)$$ instead of $$O(b^d)\sim O(b^d\cdot {b})$$

Q:

Does the try in the last bullet point about redundant paths and the relation "a factor of b" right? If not, what is the cause of the relation "a factor of b" in "any kind of graph search which stores every expanded node in the explored set"?

Edited:

Here I offer the summary of the chat related with the answer inspired by this advice:

chat_1 (this room has been removed maybe by the moderator due to that it is "not worth retaining which are inactive for 7 days")

1. The reason why thinking "a factor of $$b$$" as multiplying $$b$$ is wrong:

1. the first paragraph says the worse upper bound by multiplying $$b$$ is strange, so "a factor of $$b$$" doesn't mean that.
2. The rest is a bit "sidetracked" because I made one mistake and the edited answer has solved with the problem. The mistake is:

instead of thinking of the outer loop as one minimal unit (this is what I thought before which may be wrong after rethoughts)

3. To help future readers understand some edits of the answer as advised by this chat message, I added the summary of one edit referred to in the above chat message here.

every explored edge is incident to at least one node in $$N_x$$

This is implied in this comment. Since maybe we may have redundant paths, edge may be incident to 2 visited nodes in $$N_x$$.

1. We can derive space complexity $$S(n)$$ is $$\Theta(f(n))$$

2. For "proportional", it is not totally same as linear. And for its formula, Kenneth Kho and I both think that $$c_2,c_4$$ can be any number instead of $$c_2,c_4>0$$ to keep the symmetric property of "proportional".

But we shouldn't do strict algebraic calculation here. Based on the symmetric and transitive property implied in the answer which can be proved, "the running time is proportional* to $$k$$" implies $$k$$ is proportional to the running time by the symmetric property and "the space complexity is proportional to $$k/b$$ or larger" implies "the space complexity is proportional to $$f(n)/b$$ or larger" by the transitive property.

The above point 2 in chat_2 have been verified by Kenneth Kho although temporarily not having got the answer poster's verification.

• Feb 2 at 2:14
• I declare my discussion with zg c above (aka chat_3) complete, notice that some bits of chat_3 are also linked in the summary. Feb 13 at 13:18
• I add that "the edited answer" in point 2 of chat_1 summary should be linked as such (evidence). Feb 13 at 13:18

The usage of "within" is a bit confusing, but I think it means the space complexity is never smaller than the time complexity divided by a factor of $$b$$. The space complexity of an algorithm is always smaller than its running time (since allocating/using $$x$$ space requires at least $$c\cdot x$$ time for some constant $$c$$), so giving an upper bound that is larger than this "trivial" upper bound would not be useful.

To show this, let's take a different perspective on the GRAPH-SEARCH function. Let $$N_x$$ be the set of nodes stored by the algorithm: the union of the explored nodes and the frontier. Note that GRAPH-SEARCH does the following repeatedly (until a termination condition is reached):

Explore an edge $$e$$ of the graph that is incident to a node in $$N_x$$ and has not been explored yet, and add the node on the other end of $$e$$ to $$N_x$$.

($$N_x$$ is a set, so the line above does not always increase the size of $$N_x$$)

Now suppose the algorithm has explored $$k$$ edges. On a graph with branching factor $$b$$, the size of the explored set (i.e. $$|N_x|$$) is at least $$k/b$$. Why? Well, every explored edge is incident to at least one node in $$N_x$$ and each of the nodes in $$N_x$$ is incident to at most $$b$$ edges, so $$k\leq |N_x|\cdot b$$.

To link this back to the time and space complexity of the algorithm, note that GRAPH-SEARCH does a constant amount of operations in between the exploration of two edges. This means the running time is proportional* to $$k$$. Similarly, the space complexity is proportional to $$|N_x|$$. The inequality above then means the space complexity is proportional to $$k/b$$ or larger, and as the running time is proportional to $$k$$, the space complexity is proportional to $$f(n)/b$$ or larger, where $$f(n)$$ denotes the running time of the algorithm.

*: I say "proportional" because asymptotic notation ($$\Theta, O, \Omega$$ and such) does not technically work here. Feel free skip the explanation below and just interpret it as asymptotic notation except with some nitpicking.

I use the notion of proportional, because

1. We do not know what the exact amount of time of a single operation, or the exact amount of space used, or the relation between these values, other than that we assume (as usual) they are some fixed constant. This means that while $$|N_x|$$, $$b$$, and $$k$$ are exact and we can prove $$|N_x|\geq k/b$$, we cannot derive an exact relation between space and time complexity of the algorithm from this formula.

2. While we can consider the asymptotic behaviour of time- and space complexity, we cannot do the same for $$b$$, as it is a parameter that is not a function of $$n$$, so does not have asymptotic behaviour.

By $$A$$ is "proportional" to $$B$$, I mean that there are constants $$c_1,c_2,c_3,c_4>0$$ such that (for all values of $$A,B$$) we have $$c_1\cdot B + c_2 \leq A \leq c_3\cdot B + c_4$$. The difference between this notion and asymptotic notation ($$\Theta, O, \Omega$$ and such) is that $$a,b$$ do not have to be functions of a variable $$n$$ that represents the input size, although