4
$\begingroup$

Is the Space Complexity O(number_rows + number_cols) for Breadth First Search on a Grid. This is an attempt to show my reasoning:

For example, the flood fill question is described here:

https://www.geeksforgeeks.org/flood-fill-algorithm-implement-fill-paint/

The flood fill algorithm using breadth first search (queue) has space complexity: O(number_rows + number_cols).

Why? Suppose you start at the top left corner (or coordinate (0,0)). Going to the right we will get at most O(number_cols) in the queue. When we reached the end of the column we can then start going down from coordinate (0, 0) giving us O(number_cows + number_cols) in the queue.

Then, is it the case that many of the questions where we use breadth first search on a grid we will get space complexity of O(number_rows + number_cols). For example:

  1. Flood Fill question above,
  2. Maze where we have to find the shortest path from start to exit,
  3. Finding number of islands (reference below)

But for 3) finding the number of islands, it looks like some people are saying the space complexity is O(number_rows * number_cols) from : https://stackoverflow.com/questions/50901203/dfs-and-bfs-time-and-space-complexities-of-number-of-islands-on-leetcode

On the other hand, I would assume that the space complexity of dfs on a grid is O(number_rows * number_cols)

The questions are as follows based on the above:

  1. Is the space complexity of breadth first search on a grid: O(number_rows + number_cols)?
  2. Is the space complexity of depth first search on a grid: O(number_rows * number_cols)?

Other references:

https://stackoverflow.com/questions/21054959/time-and-space-complexity-for-breadth-first-search

https://stackoverflow.com/questions/4261112/time-and-space-complexities-of-breadth-first-search

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
4
$\begingroup$

It depends what you mean by a "on a grid".

If you mean that you are working with the graph of a complete grid, with number_rows * number_cols vertices (one for each grid point) and an edge between every pair of adjacent vertices:

Yes, that's correct. The asymptotic time complexity of both is O(number_rows * number_cols), and the asymptotic space complexity is O(number_rows + number_cols) for BFS or O(number_rows * number_cols) for DFS.

If you mean that you are working with a graph that is a subgraph of a complete grid, then:

No, that's incorrect. The asymptotic time complexity of both is O(number_rows * number_cols), and the asymptotic space complexity of both could be as large as O(number_rows * number_cols), as explained in https://stackoverflow.com/a/50912382/781723.

Improve this answer
$\endgroup$
5
  • $\begingroup$ But what does this mean from Worst-case space complexity for BFS is indeed not O(max(N, M)): it's Theta(N*M) even when we're considering simple grid. (from stackoverflow.com/questions/50901203/…) $\endgroup$
    – Meem
    Mar 30, 2019 at 4:30
  • $\begingroup$ Assume there are $c$ columns and $r$ rows. Each "node" (cell in grid) has 4 edges (left, right, up, down). This means there are $m = 4cr$ edges and $n = cr$ nodes. So it is still $O(\max(n, m))$. Don't mix up $c$ and $r$ with $n$ and $m$ as these are distinct and different values. $\endgroup$
    – ryan
    Mar 30, 2019 at 5:10
  • $\begingroup$ @Meem, see updated answer. $\endgroup$
    – D.W. ♦
    Mar 30, 2019 at 18:28
  • $\begingroup$ I am very confused. @ryan "So it is still 𝑂(max(𝑛,𝑚))", but the link says that "is indeed not O(max(N, M))" but theta(N * M) where "where M is the number of rows and N is the number of columns.". By "graph that is a subgraph of complete grid" do you mean that the red dot in the link id connected to all the nodes i.e. center connected to all the intersections caused by the vertical and horizontal lines crossing each other? $\endgroup$
    – Meem
    Mar 31, 2019 at 19:33
  • $\begingroup$ It is confusing because variables are being used without being defined. That's a recipe for confusion. I'm guessing that ryan intends that n = number of vertices, m = number of edges, r = number of rows, c = number of columns. As ryan explains, don't mix up $c$ and $r$ with $n$ and $m$. The term subgraph is defined in standard places, e.g., mathworld.wolfram.com/Subgraph.html or en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#S. $\endgroup$
    – D.W. ♦
    Mar 31, 2019 at 19:57

Your Answer

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

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