0
$\begingroup$

If we have a flood fill algorithm which, given a number of centres reprenting pixels on an image, runs a BFS flood-fill on them, checking the pixels 4 neighbours, changing their colours and adding them onto the queue to have their own neighbours processed if they have not been. What is the runtime, It seems it would be O(n) where n is the number of pixels but some sources have said it should be O(4^n). And how would this runtime change if the number of centres were changed, such that it was a multiple or fraction of n.

$\endgroup$
1
$\begingroup$

Suppose there are n pixels on the screen.

We add the neighbours onto the queue only if they haven't yet been processed.

This way a pixel is added onto the colouring queue only if it hasn't been coloured yet.

Thus a pixel can be added onto the queue for a maximum of 1 time.

So if there are n pixels, then at most n additions would be done to the queue and thus n operations would be needed to colour the entire display.

It doesn't matter if number of centres are increased or decreased since each pixel would need to be added onto the queue at most once.

Thus the complexity would remain O(n) in both the cases.

Sources that claim the complexity to be O(4^n) are considering a brute force approach where we don't remember the pixels we have already coloured and end up colouring it over and over again.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.