If i have an image consisting of n pixels what will be the complexity of classifying it using a convolutional neural network, expressed in big-o notation? (assuming my cnn is already trained)
In a CNN, the number of features in each feature map is at most a constant times the number of input pixels $n$ (typically the constant is < 1). Convolving a fixed size filter across an image with $n$ pixels takes $O(n)$ time, since each output is just the sum product between $k$ pixels in the image, and $k$ weights in the filter, and $k$ doesn't vary with $n$. Similarly, any max or avg pooling operation doesn't take more than linear time in the input size. Therefore, the overall runtime is still linear.