Yeah, indeed, the input and output images have fixed sizes, it's just the kernel that changes. But in the case of erosions and dilations they stay within the image bounds. There's no need to extend the image with the size of the kernel, as you'd do in other filters if you want proper boundary conditions. If you need to extend the image, then it's no longer O(1).