Question

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

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top