Complexity of BFS

BFS visits each node once and examines each edge once. If the graph has $V$ nodes and $E$ edges, BFS runs in $O(V + E)$ time. Queue operations (push and pop) take $O(1)$ each. Marking nodes as visited takes $O(1)$ per node. The space complexity is $O(V)$ for the queue and visited array.

In the worst case, all nodes could be in the queue at once. For a grid, $V = rows \times cols$ and $E$ is about $4V$ (or $8V$ with diagonals), so BFS runs in $O(rows \times cols)$ time.