What are the advantages of FC layers over Conv layers? I am trying to think of scenarios where a fully connected (FC) layer is a better choice than a convolution layer.
In terms of time complexity, are they the same?
I know that convolution can represent a wider variety of features so when would one prefer to use a FC layer?
 A: As mentioned in the wiki article, convolutional layers are optimized for translationally-invariant parameters, such as pixel intensities in images and video. If your parameters represent a discretized sample of a continuous variable, such as space or time, then translational invariance means that every window of the parameters (such as a 10x10 pixel slice of the image) is to some extent similar to every other and benefits to be pre-processed (filtered) by the same means. In this case, you can select a convolutional layer, and by doing so, enforce your knowledge about the symmetries of this world onto your neuronal network.
On the other hand side, if you have a bunch of input parameters whose indices are not related to their meaning (e.g. params=[temperature, pressure, volume, loudness, brightness, ...]), then they are most certainly not translationally-invariant, the intrinsic assumptions of the convolution layer are not met, and it is only detremental to use it
A: The strength of convolutional layers over fully connected layers is precisely that they represent a narrower range of features than fully-connected layers. A neuron in a fully connected layer is connected to every neuron in the preceding layer, and so can change if any of the neurons from the preceding layer changes. A neuron in a convolutional layer, however, is only connected to "nearby" neurons from the preceding layer within the width of the convolutional kernel. As a result, the neurons from a convolutional layer can represent a narrower range of features in the sense that the activation of any one neuron is insensitive to the activations of most of the neurons from the previous layer.
Restricting the range of features in this way can be useful in cases where we expect most of the information to be local. In image classification, for example, a bird will look like a bird based on the pixels in the location of the bird, regardless of its location in the image and regardless of whether there is also a car somewhere else in the image. The utility of this prior expectation is born out by the observation that even CNNs with totally random weights provide features that are nearly as useful for classification as fully-trained CNNs.
