I thought I remembered something about this, so I googled around a bit and the consensus appears to be that flood fill algorithms are a variant of a depth-first search algorithm.
If this is indeed true (I didn't do exhaustive research here), then we can simply look at the time and space complexity of a depth-first search to find the worst case:
Quote:
|
Originally Posted by depth first WikiPedia
The time and space analysis of DFS differs according to its application area. In theoretical computer science, DFS is typically used to traverse an entire graph, and takes time ?(|V| + |E|), linear in the size of the graph. In these applications it also uses space O(|V|) in the worst case to store the stack of vertices on the current search path as well as the set of already-visited vertices.
|
Which, if I'm reading it correctly, suggests the worst case scenario is indeed one entry per pixel.