Back to course home
0% completed
Vote For New Content
Why space complexity for BFS is min (M*N) ? what does it even mean?
Mikhail Putilov
Jul 28, 2022
Why space complexity for BFS is min (M*N) ? what does it even mean?
5
0
Comments
Comments
Design Gurus3 years ago
This means, if M < N then the space complexity will be O(M) otherwise O(N).
Let's say if M < N, we will not have more than O(M) elements in the queue, hence the space complexity.
R
Richard Yuan3 years ago
I think there is a typo, which is causing the confusion. It should be O(min(M,N)), not O(min(M*N)).
Design Gurus3 years ago
That's right, it should have been O(min(M,N)) .
On this page