In a sense it uses half a byte per pixel, but Nils M Holm's suggested implementation is to reserve 16 colors for the flood-fill algorithm, because you don't need to remember the color of the pixels you're flood-filling, so you can overwrite them with the flood-fill algorithm's state. The path is saved in those same 16 colors. This reduces your available color space, assuming 8-bit color, from 256 colors to 240 colors, which means you get 7.91-bit color instead of 8-bit color. So it actually only uses 0.09 bits per pixel, which at 1024×768 is 9154 bytes.

If you were to instead use a bounded area of the heap with 4 bits per pixel, as you are suggesting, your bound would be 393216 bytes.

However, it's not totally clear that that's the right way to account for it, because if you have a 256-color image that you have to reduce to 240 colors to have space for this algorithm, there isn't an obvious way to get back the lost colors by storing 9154 bytes somewhere else. You might be able to do something like pick the least popular 16 colors from the image (which occupy a maximum of 49152 pixels and usually less), store a bitmap telling where they were (98304 bytes), store the colors of the marked pixels into a 24576-byte array, replace them with some neutral color, run the flood fill, and then restore the colors. But, while that uses significantly less than 393216 bytes, it still uses a lot more than 9154 bytes, and it's probably pretty slow on the kind of computer where you'd be trying to do something like this.

At the other extreme, if your 256-color image actually only used the 216 "web-safe" colors (#000, #003, #006, ... #030, #033, etc.), you'd already have 16 leftover colors available. And freeing up 16 colors on a 16-bit or 24-bit TrueColor display would damage the image quality only imperceptibly.

I remember Mario Paint on Super Nintendo visibly flood-filling an area, but a computer that paints in modern image formats is probably not going to mind temporary allocation of a few hundred K. There are some fun opportunities to optimize, though, like checking a cache line of pixels at a time, or maybe tiling the image in 16-pixel squares using the same algorithm, and then cleaning up the edges.