Flood fill vs depth first search
The Flood Fill algorithm is a particular case of the Depth First Seach algorithm, on regular mesh graphs:


Wikipedia indicates that they do not work on the same kind of data:


The Flood Fill algorithm is "an algorithm that determines the area connected to a given node in a multi-dimensional array."
The Depth First Seach algorithm is "an algorithm for traversing or searching tree or graph data structures".

A multi-dimensional array (and the kind of neighborhood considered in the flood fill algorithm) is a particular case of graph, extremely regular.


In any case, the complexity is clearly within $O(n)$ where $n$ is the number of nodes being colored (for both problems).