Tighter complexity for problem 19.3 (Paint a Boolean Matrix)

#1

I have some issues when trying to understand the space complexity of problem 19.3 (Paint a Boolean Matrix).

The book says the space complexity of BFS is O(m+n) because there are at most O(m+n) vertices that are at the same distance from a given entry. However, I think a tighter estimation may be O(sqrt(m^2 + n^2)). For example, when the paint position starts at the corner and all the matrix is true, the max queue size is the diagonal, sqrt(m^2 + n^2). Also, when beginning at the center, the max queue size is twice of the diagonal, 2*sqrt(m^2 + n^2).

Moreover, the book does not say about the space complexity of DFS solution which I assume also the same with the BFS, O(m+n). However, the space complexity of the DFS is O(m*n), when the paint position starts at the corner and all the matrix is true. It would be much clearer if the book have a sentence about the space complexity.

0 Likes
#2

Hey Duc,

I was thinking this question for a while—how many elements in queue simultaneously? I think the maximum is about O(2m + 2n), basically it is the border of the region. Although I can say the traversing order plays an important parameter here, I think our space complexity analysis is correct but the text definitely needs some overhauls.

Also, for your question on DFS space complexity, I think the space complexity shall be O(m*n) as you said if the calling stack contains all elements of all elements. For example, DFS recursive calls in spiral order.

0 Likes
#3

Hi @tsunghsienlee , I came across this StackOverflow answer
which describes the space complexity for BFS on a matrix as Theta(m * n). The explanation there is that eventually we will have all the leaves of the graph in the queue. This made me confused about what would be the worst case complexity for using BFS on 2D matrix. Does that sound right to you? If yes, then does it change the BFS space complexity for this question in the book as well?

0 Likes
#4

I agree with @rhlp. Given the counter example in the answer on StackOverflow and this explanation on StackExchange, I think the space complexity of BFS for the problem 19.3 is for a subgraph of a grid which is O(m * n) where m and n are the number of rows and columns of the grid. If we consider the whole grid where all nodes are connected, I think O(m + n) is correct, but it is not the case of the problem 19.3.

0 Likes