patternMinor
Is Breadth First Search Space Complexity on a Grid different?
Viewed 0 times
spacegridsearchbreadthdifferentfirstcomplexity
Problem
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:
path from start to exit,
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:
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
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:
- Flood Fill question above,
- Maze where we have to find the shortest
path from start to exit,
- 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:
- Is the space complexity of breadth first search on a grid: O(number_rows + number_cols)?
- 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
Solution
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.
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.
Context
StackExchange Computer Science Q#106233, answer score: 4
Revisions (0)
No revisions yet.