# Do GANs have constant running time?

After the model is trained, you just need to input random noise and the generator will output an image, does this mean GANs have constant running time ? I'm asking about both naïve GAN and variants of GAN

• constant running time with respect to what? Nov 27, 2023 at 12:36
• What do you mean? I just asked about the running time complexity of GAN, does the model have a constant running time or what?
– user78202
Nov 27, 2023 at 14:38

The question is a bit ill defined... usually when we want some bound on the running time, we have to say with respect to what

For example:

• sorting is O(nlogn) wrt the size of the input
• Transformer is O(n^2 * d) wrt to the number of input words (or number of patches)
• Diffusion models have O(1) complexity if we just consider the forward/backward diffusion

Now, as you can see, the problem is "hat are we considering for the measure"... sure if you encode GAN will Fully connected layers, you just have the n^2 for matrix multiplication... however, diffusion models have N step of diffusion to account for, but with the big-O notation taht N is canceled as it is just a constant

• Is inference time different from running time, I read from the internet that GAN's inference time is faster than diffusion model ?
– user78202
Nov 27, 2023 at 17:26
• @David yes, but for the definition of computational complexity, you cannot see such difference, as they differ by a constant... GANs only need 1 forward pass, diffusion models usually in the order of tens of forward passes Nov 27, 2023 at 17:35
• So both run at constant time ? Because you can define the number of steps in diffusion model
– user78202
Nov 27, 2023 at 17:42
• @David exactly, from a computational point of view, since it's constant, it's omitted from the analysis (though, in real life, you have definitely to consider it) Nov 27, 2023 at 20:54
• I guess diffusion model is better than GAN in every aspect ?
– user78202
Nov 30, 2023 at 20:33